- О сходимости методов градиента политики к равновесию Нэша в общих стохастических играх(arXiv)
Автор:Анжелики Джанноу, Кириакос Лотидис, Панайотис Мертикопулос, Эммануил-Василеос Влатакис-Гкарагкунис
Аннотация : обучение в стохастических играх является общеизвестно сложной проблемой, потому что, в дополнение к стратегическим решениям друг друга, игроки также должны учитывать тот факт, что сама игра развивается с течением времени, возможно, очень сложным образом. . Из-за этого свойства сходимости популярных алгоритмов обучения, таких как градиент политики и его варианты, плохо изучены, за исключением определенных классов игр (таких как потенциальные игры или игры с двумя игроками с нулевой суммой). Ввиду этого мы исследуем долгосрочное поведение методов градиента политики по отношению к политике равновесия Нэша, которая является стационарной второго порядка (SOS) в смысле, аналогичном типу условий достаточности, используемых в оптимизации. Наш первый результат заключается в том, что политики SOS локально привлекают с высокой вероятностью, и мы показываем, что траектории градиента политики с оценками градиента, полученными алгоритмом REINFORCE, достигают скорости сходимости квадрата расстояния O(1/n−−√), если шаг метода размер подобран правильно. Впоследствии, специализируясь на классе детерминированных политик Нэша, мы показываем, что эта скорость может быть значительно улучшена, и что в этом случае методы градиента политики сходятся за конечное число итераций.
2. Градиент децентрализованной политики для изучения равновесия Нэша в стохастических играх с общей суммой(arXiv)
Аннотация: мы изучаем изучение равновесия Нэша в стохастической игре с общей суммой с неизвестной функцией плотности вероятности перехода. Агенты предпринимают действия в текущем состоянии среды, и их совместные действия влияют на изменение состояния среды и их немедленные вознаграждения. Каждый агент наблюдает только за состоянием окружающей среды и своим немедленным вознаграждением и ничего не знает о действиях или немедленных вознаграждениях других. Вводятся понятия взвешенного асимптотического равновесия по Нэшу с вероятностью 1 и по вероятности. Для случая с точными псевдоградиентами мы разрабатываем двухпетлевой алгоритм по эквивалентности задач равновесия по Нэшу и вариационного неравенства. Во внешнем цикле мы последовательно обновляем построенное строго монотонное вариационное неравенство, обновляя проксимальный параметр, а во внутреннем цикле используем экстраградиентный алгоритм с одним вызовом для решения построенного вариационного неравенства. Показано, что если соответствующее вариационное неравенство Минти имеет решение, то разработанный алгоритм сходится к k^{1/2}-взвешенному асимптотическому равновесию Нэша. Кроме того, для случая с неизвестными псевдоградиентами мы предлагаем децентрализованный алгоритм, в котором оценка градиента G(PO)MDP для псевдоградиента обеспечивается моделированием методом Монте-Карло. Достигнута сходимость к k^{1/4}-взвешенному асимптотическому равновесию Нэша по вероятности
3.Стохастические игры с общими функциями выплат(arXiv)
Автор:Янос Флеш, Эйлон Солан
Аннотация: мы рассматриваем многопользовательские стохастические игры, в которых выигрыш каждого игрока является ограниченной и измеримой по Борелю функцией бесконечной игры. Используя обобщение техники Мартина (1998) и Майтры и Саддерта (1998), мы показываем четыре различных результата существования. В каждой стохастической игре для любого ε > 0 верно, что (i) у каждого игрока есть стратегия, гарантирующая в каждой подыгре, что выигрыш этого игрока не ниже его maxmin значения до ε, (ii) существует профиль стратегии, при котором в каждой подигре выигрыш каждого игрока равен, по крайней мере, его минимальному максимальному значению вплоть до ε, (iii) игра допускает коррелированное ε-равновесие в экстенсивной форме, и (iv) существует подигра, допускающая ε-равновесие.
