Множини Мазера каскаду, породженого FTRL-алгоритмом двоагентної гри з нульовою сумою та мішаними стратегіями
DOI:
https://doi.org/10.3842/umzh.v77i6.9034Ключові слова:
каскад, FTRL-алгоритм, монотонне крутне відображення, множина МазераАнотація
УДК 517.9
Встановлено умови, за яких двовимірний каскад, породжений FTRL-алгоритмом двоагентної гри з нульовою сумою та мішаними стратегіями, визначається крутним відображенням площини. Для зазначеного каскаду доведено існування множин Мазера, що відповідають числам обертання з певного інтервалу. У такий спосіб пояснено, чому в комп'ютерних експериментах орбіти каскаду розташовуються на замкнених кривих і в певному сенсі мають властивість локальної опуклості.
Посилання
1. E. Hairer, C. Lubich, G. Wanner, Geometric numerical integration, Structure-preserving algorithms for ordinary differential equations, 2nd ed., Springer Ser. Comput. Math., 31, Springer, Berlin (2006); DOI: 10.1007/3-540-30666-8. DOI: https://doi.org/10.1007/3-540-30666-8
2. G. Benettin, A. Giorgilli, On the Hamiltonian interpolation of near-to-the-identity symplectic mappings with application to symplectic integration algorithms, J. Stat. Phys., 74, № 5-6, 1117–1143 (1994); DOI: 10.1007/BF02188219. DOI: https://doi.org/10.1007/BF02188219
3. J. Hofbauer, Evolutionary dynamics for bimatrix games: a Hamiltonian system?, J. Math. Biol., 34, № 5-6, 675–688 (1996); DOI: 10.1007/BF02409754. DOI: https://doi.org/10.1007/BF02409754
4. J. P. Bailey, G. Gidel, G. Piliouras, Finite regret and cycles with fixed step-size via alternating gradient descent-ascent, Proceedings of Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, 125, 391–407 (2020); https://proceedings.mlr.press/v125/bailey20a.html.
5. J. P. Bailey, G. Piliouras, Multi-agent learning in network zero-sum games is a Hamiltonian system, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS'19, Montreal, QC, Canada, May 13–17, 2019, International Foundation for Autonomous Agents and Multiagent Systems, 233–241 (2019); http://dl.acm.org/citation.cfm?id=3306127.
6. J. P. Bailey, G. Piliouras, Multiplicative weights update in zero-sum games, Proceedings of the 2018 ACM Conference on Economics and Computation, EC'18, Association for Computing Machinery, New York, 321–338 (2018); DOI: 10.1145/3219166.3219235. DOI: https://doi.org/10.1145/3219166.3219235
7. P. Mertikopoulos, C. Papadimitriou, G. Piliouras, Cycles in adversarial regularized learning, Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January~7–10, 2018, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); Association for Computing Machinery (ACM), New York, 2703–2717 (2018); dl.acm.org/citation.cfm?id=3175476. DOI: https://doi.org/10.1137/1.9781611975031.172
8. G. Piliouras, S. Jeff, J. S. Shamma, Optimization despite chaos: convex relaxations to complex limit sets via Poincare recurrence, 861–873 (2014); https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.64. DOI: https://doi.org/10.1137/1.9781611973402.64
9. S. Aubry, P. Y. Le Daeron, The discrete Frenkel–Kontorova model and its extensions. I. Exact results for the ground-states, Phys. D, 8, № 3, 381–422 (1983); DOI: 10.1016/0167-2789(83)90233-6. DOI: https://doi.org/10.1016/0167-2789(83)90233-6
10. C. Golé, Symplectic twist maps, Advanced Series in Nonlinear Dynamics, 18, World Sci. Publ. Co., Inc., River Edge, NJ (2001); DOI: 10.1142/9789812810762. DOI: https://doi.org/10.1142/9789812810762
11. J. N. Mather, Existence of quasiperiodic orbits for twist homeomorphisms of the annulus, Topology, 21, № 4, 457–467 (1982); DOI: 10.1016/0040-9383(82)90023-4. DOI: https://doi.org/10.1016/0040-9383(82)90023-4
12. J. Moser, Recent developments in the theory of Hamiltonian systems, SIAM Rev., 28, № 4, 459–485 (1986); DOI: 10.1137/1028153. DOI: https://doi.org/10.1137/1028153
13. J. Moser, Monotone twist mappings and the calculus of variations, Ergodic Theory and Dynam. Systems, 6, № 3, 401–413 (1986); DOI: 10.1017/S0143385700003588. DOI: https://doi.org/10.1017/S0143385700003588
14. V. I. Arnold, Mathematical methods of classical mechanics, 2nd ed., Grad. Texts Math., 60, Springer-Verlag, New York (1989); DOI: 10.1007/978-1-4757-2063-1. DOI: https://doi.org/10.1007/978-1-4757-2063-1
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2025 V. Kolner, I. Parasyuk
Ця робота ліцензується відповідно до ліцензії Creative Commons Attribution 4.0 International License.
