On the Power of Perturbation under Sampling in Solving Extensive-Form Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911087660630016 |
|---|---|
| author | Masaka, Wataru Sakamoto, Mitsuki Abe, Kenshi Ariu, Kaito Sandholm, Tuomas Iwasaki, Atsushi |
| author_facet | Masaka, Wataru Sakamoto, Mitsuki Abe, Kenshi Ariu, Kaito Sandholm, Tuomas Iwasaki, Atsushi |
| contents | We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving imperfect-information extensive-form games under sampling, where payoffs are estimated from sampled trajectories. While optimistic algorithms are effective under full feedback, they often become unstable in the presence of sampling noise. Payoff perturbation offers a promising alternative for stabilizing learning and achieving \textit{last-iterate convergence}. We present a unified framework for \textit{Perturbed FTRL} algorithms and study two variants: PFTRL-KL (standard KL divergence) and PFTRL-RKL (Reverse KL divergence), the latter featuring an estimator with both unbiasedness and conditional zero variance. While PFTRL-KL generally achieves equivalent or better performance across benchmark games, PFTRL-RKL consistently outperforms it in Leduc poker, whose structure is more asymmetric than the other games in a sense. Given the modest advantage of PFTRL-RKL, we design the second experiment to isolate the effect of conditional zero variance, showing that the variance-reduction property of RKL improve last-iterate performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16600 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Power of Perturbation under Sampling in Solving Extensive-Form Games Masaka, Wataru Sakamoto, Mitsuki Abe, Kenshi Ariu, Kaito Sandholm, Tuomas Iwasaki, Atsushi Computer Science and Game Theory Machine Learning Multiagent Systems We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving imperfect-information extensive-form games under sampling, where payoffs are estimated from sampled trajectories. While optimistic algorithms are effective under full feedback, they often become unstable in the presence of sampling noise. Payoff perturbation offers a promising alternative for stabilizing learning and achieving \textit{last-iterate convergence}. We present a unified framework for \textit{Perturbed FTRL} algorithms and study two variants: PFTRL-KL (standard KL divergence) and PFTRL-RKL (Reverse KL divergence), the latter featuring an estimator with both unbiasedness and conditional zero variance. While PFTRL-KL generally achieves equivalent or better performance across benchmark games, PFTRL-RKL consistently outperforms it in Leduc poker, whose structure is more asymmetric than the other games in a sense. Given the modest advantage of PFTRL-RKL, we design the second experiment to isolate the effect of conditional zero variance, showing that the variance-reduction property of RKL improve last-iterate performance. |
| title | On the Power of Perturbation under Sampling in Solving Extensive-Form Games |
| topic | Computer Science and Game Theory Machine Learning Multiagent Systems |
| url | https://arxiv.org/abs/2501.16600 |