Newton Optimization on Helmholtz Decomposition for Continuous Games

Many learning problems involve multiple agents optimizing different interactive functions. In these problems, the standard policy gradient algorithms fail due to the non-stationarity of the setting and the different interests of each agent. In fact, algorithms must take into account the complex dyna...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the ... AAAI Conference on Artificial Intelligence 2021-05, Vol.35 (13), p.11325-11333
Main Authors: Ramponi, Giorgia, Restelli, Marcello
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c218t-f6761061c20f5015894c57030b129305946ebbb03f3a1ff966180efa1949adfe3
cites
container_end_page 11333
container_issue 13
container_start_page 11325
container_title Proceedings of the ... AAAI Conference on Artificial Intelligence
container_volume 35
creator Ramponi, Giorgia
Restelli, Marcello
description Many learning problems involve multiple agents optimizing different interactive functions. In these problems, the standard policy gradient algorithms fail due to the non-stationarity of the setting and the different interests of each agent. In fact, algorithms must take into account the complex dynamics of these systems to guarantee rapid convergence towards a (local) Nash equilibrium. In this paper, we propose NOHD (Newton Optimization on Helmholtz Decomposition), a Newton-like algorithm for multi-agent learning problems based on the decomposition of the dynamics of the system in its irrotational (Potential) and solenoidal (Hamiltonian) component. This method ensures quadratic convergence in purely irrotational systems and pure solenoidal systems. Furthermore, we show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones. Finally, we empirically compare the NOHD's performance with that of state-of-the-art algorithms on some bimatrix games and continuous Gridworlds environment.
doi_str_mv 10.1609/aaai.v35i13.17350
format article
fullrecord <record><control><sourceid>crossref</sourceid><recordid>TN_cdi_crossref_primary_10_1609_aaai_v35i13_17350</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1609_aaai_v35i13_17350</sourcerecordid><originalsourceid>FETCH-LOGICAL-c218t-f6761061c20f5015894c57030b129305946ebbb03f3a1ff966180efa1949adfe3</originalsourceid><addsrcrecordid>eNotkFFLwzAUhYMoOOZ-gG_9A6339iZp8yhVt8FwL_oc0ppgpG1K0ynu19ttHg6cc7hwHz7G7hEylKAejDE--ybhkTIsSMAVW-RU8JS4LK_njkKlgpS6ZasYv2AWV4hYLFj1an-m0Cf7YfKdP5rJz2P2xrbdZ2inY_Jkm9ANIfrzyYUxqUI_-f4QDjFZm87GO3bjTBvt6j-X7P3l-a3apLv9els97tImx3JKnSwkgsQmBycARal4IwogqDFXBEJxaeu6BnJk0DklJZZgnUHFlflwlpYML3-bMcQ4WqeH0Xdm_NUI-gRCn0DoCwh9BkF_ek5SXQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Newton Optimization on Helmholtz Decomposition for Continuous Games</title><source>Freely Accessible Journals</source><creator>Ramponi, Giorgia ; Restelli, Marcello</creator><creatorcontrib>Ramponi, Giorgia ; Restelli, Marcello</creatorcontrib><description>Many learning problems involve multiple agents optimizing different interactive functions. In these problems, the standard policy gradient algorithms fail due to the non-stationarity of the setting and the different interests of each agent. In fact, algorithms must take into account the complex dynamics of these systems to guarantee rapid convergence towards a (local) Nash equilibrium. In this paper, we propose NOHD (Newton Optimization on Helmholtz Decomposition), a Newton-like algorithm for multi-agent learning problems based on the decomposition of the dynamics of the system in its irrotational (Potential) and solenoidal (Hamiltonian) component. This method ensures quadratic convergence in purely irrotational systems and pure solenoidal systems. Furthermore, we show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones. Finally, we empirically compare the NOHD's performance with that of state-of-the-art algorithms on some bimatrix games and continuous Gridworlds environment.</description><identifier>ISSN: 2159-5399</identifier><identifier>EISSN: 2374-3468</identifier><identifier>DOI: 10.1609/aaai.v35i13.17350</identifier><language>eng</language><ispartof>Proceedings of the ... AAAI Conference on Artificial Intelligence, 2021-05, Vol.35 (13), p.11325-11333</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c218t-f6761061c20f5015894c57030b129305946ebbb03f3a1ff966180efa1949adfe3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Ramponi, Giorgia</creatorcontrib><creatorcontrib>Restelli, Marcello</creatorcontrib><title>Newton Optimization on Helmholtz Decomposition for Continuous Games</title><title>Proceedings of the ... AAAI Conference on Artificial Intelligence</title><description>Many learning problems involve multiple agents optimizing different interactive functions. In these problems, the standard policy gradient algorithms fail due to the non-stationarity of the setting and the different interests of each agent. In fact, algorithms must take into account the complex dynamics of these systems to guarantee rapid convergence towards a (local) Nash equilibrium. In this paper, we propose NOHD (Newton Optimization on Helmholtz Decomposition), a Newton-like algorithm for multi-agent learning problems based on the decomposition of the dynamics of the system in its irrotational (Potential) and solenoidal (Hamiltonian) component. This method ensures quadratic convergence in purely irrotational systems and pure solenoidal systems. Furthermore, we show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones. Finally, we empirically compare the NOHD's performance with that of state-of-the-art algorithms on some bimatrix games and continuous Gridworlds environment.</description><issn>2159-5399</issn><issn>2374-3468</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNotkFFLwzAUhYMoOOZ-gG_9A6339iZp8yhVt8FwL_oc0ppgpG1K0ynu19ttHg6cc7hwHz7G7hEylKAejDE--ybhkTIsSMAVW-RU8JS4LK_njkKlgpS6ZasYv2AWV4hYLFj1an-m0Cf7YfKdP5rJz2P2xrbdZ2inY_Jkm9ANIfrzyYUxqUI_-f4QDjFZm87GO3bjTBvt6j-X7P3l-a3apLv9els97tImx3JKnSwkgsQmBycARal4IwogqDFXBEJxaeu6BnJk0DklJZZgnUHFlflwlpYML3-bMcQ4WqeH0Xdm_NUI-gRCn0DoCwh9BkF_ek5SXQ</recordid><startdate>20210518</startdate><enddate>20210518</enddate><creator>Ramponi, Giorgia</creator><creator>Restelli, Marcello</creator><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20210518</creationdate><title>Newton Optimization on Helmholtz Decomposition for Continuous Games</title><author>Ramponi, Giorgia ; Restelli, Marcello</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c218t-f6761061c20f5015894c57030b129305946ebbb03f3a1ff966180efa1949adfe3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><toplevel>online_resources</toplevel><creatorcontrib>Ramponi, Giorgia</creatorcontrib><creatorcontrib>Restelli, Marcello</creatorcontrib><collection>CrossRef</collection><jtitle>Proceedings of the ... AAAI Conference on Artificial Intelligence</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ramponi, Giorgia</au><au>Restelli, Marcello</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Newton Optimization on Helmholtz Decomposition for Continuous Games</atitle><jtitle>Proceedings of the ... AAAI Conference on Artificial Intelligence</jtitle><date>2021-05-18</date><risdate>2021</risdate><volume>35</volume><issue>13</issue><spage>11325</spage><epage>11333</epage><pages>11325-11333</pages><issn>2159-5399</issn><eissn>2374-3468</eissn><abstract>Many learning problems involve multiple agents optimizing different interactive functions. In these problems, the standard policy gradient algorithms fail due to the non-stationarity of the setting and the different interests of each agent. In fact, algorithms must take into account the complex dynamics of these systems to guarantee rapid convergence towards a (local) Nash equilibrium. In this paper, we propose NOHD (Newton Optimization on Helmholtz Decomposition), a Newton-like algorithm for multi-agent learning problems based on the decomposition of the dynamics of the system in its irrotational (Potential) and solenoidal (Hamiltonian) component. This method ensures quadratic convergence in purely irrotational systems and pure solenoidal systems. Furthermore, we show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones. Finally, we empirically compare the NOHD's performance with that of state-of-the-art algorithms on some bimatrix games and continuous Gridworlds environment.</abstract><doi>10.1609/aaai.v35i13.17350</doi><tpages>9</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2159-5399
ispartof Proceedings of the ... AAAI Conference on Artificial Intelligence, 2021-05, Vol.35 (13), p.11325-11333
issn 2159-5399
2374-3468
language eng
recordid cdi_crossref_primary_10_1609_aaai_v35i13_17350
source Freely Accessible Journals
title Newton Optimization on Helmholtz Decomposition for Continuous Games
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-01T13%3A56%3A36IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Newton%20Optimization%20on%20Helmholtz%20Decomposition%20for%20Continuous%20Games&rft.jtitle=Proceedings%20of%20the%20...%20AAAI%20Conference%20on%20Artificial%20Intelligence&rft.au=Ramponi,%20Giorgia&rft.date=2021-05-18&rft.volume=35&rft.issue=13&rft.spage=11325&rft.epage=11333&rft.pages=11325-11333&rft.issn=2159-5399&rft.eissn=2374-3468&rft_id=info:doi/10.1609/aaai.v35i13.17350&rft_dat=%3Ccrossref%3E10_1609_aaai_v35i13_17350%3C/crossref%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c218t-f6761061c20f5015894c57030b129305946ebbb03f3a1ff966180efa1949adfe3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true