無知マルコフゲームへのオンライン学習：実驗的ナッシュバリュー後悔と非定常性への適応

arXiv:2602.07205v1 Announce Type: new 要約：ここでは、対局者の行動やポリシーが観測されない無知マルコフゲームにおけるオンライン学習を研究します。この設定において、Tian ら (2021) は、外部後悔をゼロにすることを達成するにはエピソード長さ $H$ に対して指数関数的な依存性を負うことが不可能であることを示しました。その後、彼らは弱い概念であるナッシュバリュー後悔へと転じ、$K$ エピソード後に後悔 $O(K^{2/3})$ を達成する V-learning アルゴリズムを提案しました。しかし、彼らのアルゴリズムと保証は問題の難易度に適応していません：対局者が固定されたポリシーに従っている場合（したがって $O(\sqrt{K})$ の外部後悔は知られている通り）であっても、彼らの結果はより弱い尺度において依然として $O(K^{2/3})$ のより悪いレートを示しています。 この論文では、これらの制限を両方とも完全に解決します。まず、私たちは対局者が固定ポリシーに従う場合に外部後悔に自然に還元される、ナッシュバリュー後悔より明らかに強力な新しい後悔概念である実驗的ナッシュバリュー後悔を導入します。さらに、この新しい尺度の下では、相手の方策の分散を定量化するパラメータ $C$ と、方策の切り替え数を示すパラメータ $L$（どちらも最多 $O(K)$）を用いることで、$O(\min \{\sqrt{K} + (CK)^{1/3},\sqrt{LK}\})$ の後悔束を達成するパラメータフリーなアルゴリズムを提案します。したがって、私らの結果は、相手がいなければ $O(\sqrt{K})$ の外部後悔、最悪の場合において $O(K^{2/3})$ のナッシュバリュー後悔という両端を復元するだけでなく、相手の方策の非定常性に自動的に適応してこれらの両端をスムーズに挿入します。これは、まず Mao ら (2022) の時系列に基づく V-learning アルゴリズムに対する新しい解析を提供することで達成されます。これにより、$ar{\eta}$ は時系列の増加率であるため $O(\eta C + \sqrt{K/\eta})$ の後悔束が確立されます。次に、私らは、相手方の潜在的非定常性に応じて適切な $\eta$ でこのアルゴリズムを適応的にリスタートする方法を示し、最終的に我らの結果に至ります。

arXiv:2602.07205v1 Announce Type: new Abstract: We study online learning in two-player uninformed Markov games, where the opponent's actions and policies are unobserved. In this setting, Tian et al. (2021) show that achieving no-external-regret is impossible without incurring an exponential dependence on the episode length $H$. They then turn to the weaker notion of Nash-value regret and propose a V-learning algorithm with regret $O(K^{2/3})$ after $K$ episodes. However, their algorithm and guarantee do not adapt to the difficulty of the problem: even in the case where the opponent follows a fixed policy and thus $O(\sqrt{K})$ external regret is well-known to be achievable, their result is still the worse rate $O(K^{2/3})$ on a weaker metric. In this work, we fully address both limitations. First, we introduce empirical Nash-value regret, a new regret notion that is strictly stronger than Nash-value regret and naturally reduces to external regret when the opponent follows a fixed policy. Moreover, under this new metric, we propose a parameter-free algorithm that achieves an $O(\min \{\sqrt{K} + (CK)^{1/3},\sqrt{LK}\})$ regret bound, where $C$ quantifies the variance of the opponent's policies and $L$ denotes the number of policy switches (both at most $O(K)$). Therefore, our results not only recover the two extremes -- $O(\sqrt{K})$ external regret when the opponent is fixed and $O(K^{2/3})$ Nash-value regret in the worst case -- but also smoothly interpolate between these extremes by automatically adapting to the opponent's non-stationarity. We achieve so by first providing a new analysis of the epoch-based V-learning algorithm by Mao et al. (2022), establishing an $O(\eta C + \sqrt{K/\eta})$ regret bound, where $\eta$ is the epoch incremental factor. Next, we show how to adaptively restart this algorithm with an appropriate $\eta$ in response to the potential non-stationarity of the opponent, eventually achieving our final results.