{"id":2104,"date":"2025-02-27T07:03:00","date_gmt":"2025-02-27T07:03:00","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/02\/27\/2502-18582\/"},"modified":"2025-02-27T07:03:00","modified_gmt":"2025-02-27T07:03:00","slug":"2502-18582","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/02\/27\/2502-18582\/","title":{"rendered":"Learning and Computation of $Phi$-Equilibria at the Frontier of Tractability"},"content":{"rendered":"

Learning and Computation of $Phi$-Equilibria at the Frontier of Tractability
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2502.18582v1 Announce Type: new
\nAbstract: $Phi$-equilibria — and the associated notion of $Phi$-regret — are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations $Phi$ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC ’24) — abbreviated as DFFPS — settled the existence of efficient algorithms when $Phi$ contains only linear maps under a general, $d$-dimensional convex constraint set $mathcal{X}$. In this paper, we significantly extend their work by resolving the case where $Phi$ is $k$-dimensional; degree-$ell$ polynomials constitute a canonical such example with $k = d^{O(ell)}$. In particular, positing only oracle access to $mathcal{X}$, we obtain two main positive results: i) a $text{poly}(n, d, k, text{log}(1\/epsilon))$-time algorithm for computing $epsilon$-approximate $Phi$-equilibria in $n$-player multilinear games, and ii) an efficient online algorithm that incurs average $Phi$-regret at most $epsilon$ using $text{poly}(d, k)\/epsilon^2$ rounds.
\n We also show nearly matching lower bounds in the online learning setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
\n From a technical standpoint, we extend the framework of DFFPS from linear maps to the more challenging case of maps with polynomial dimension. At the heart of our approach is a polynomial-time algorithm for computing an expected fixed point of any $phi : mathcal{X} to mathcal{X}$ based on the ellipsoid against hope (EAH) algorithm of Papadimitriou and Roughgarden (JACM ’08). In particular, our algorithm for computing $Phi$-equilibria is based on executing EAH in a nested fashion — each step of EAH itself being implemented by invoking a separate call to EAH.<\/div>\n

\t

\n
<\/BR>
\n Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, Tuomas Sandholm
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Learning and Computation of $Phi$-Equilibria at the Frontier of Tractability arXiv:2502.18582v1 Announce Type: new Abstract: $Phi$-equilibria — and the associated notion of $Phi$-regret — are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations $Phi$ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,1876,113,112],"tags":[778,1877,1697],"class_list":["post-2104","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-gt","category-cs-lg","category-stat-ml","tag-algorithm","tag-equilibria","tag-phi"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/2104"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=2104"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/2104\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=2104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=2104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=2104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}