RVσ(t): A unifying approach to performance and convergence in online multiagent learning

Bikramjit Banerjee; Jing Peng

doi:10.1145/1160633.1160775

RV_σ(t): A unifying approach to performance and convergence in online multiagent learning

Bikramjit Banerjee, Jing Peng

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

We present a new multiagent learning algorithm (RV_σ(t)) that can guarantee both no-regret performance (all games) and policy convergence (some games of arbitrary size). Unlike its predecessor ReDVaLeR, it (1) does not need to distinguish whether its opponents are self-play or otherwise non-stationary, (2) is allowed to know its portion of any equilibrium that, we argue, leads to convergence in some games in addition to no-regret. Although the regret of RV_σ(t) is analyzed in continuous time, we show that it grows slower than in other no-regret techniques like GIGA and GIGA-WoLF. We show that RV_σ(t) can converge to coordinated behavior in coordination games, while GIGA, GIGA-WoLF may converge to poorly coordinated (mixed) behaviors.

Original language	English
Title of host publication	Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems
Pages	798-800
Number of pages	3
DOIs	https://doi.org/10.1145/1160633.1160775
State	Published - 2006
Event	Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS - Hakodate, Japan Duration: 8 May 2006 → 12 May 2006

Publication series

Name	Proceedings of the International Conference on Autonomous Agents
Volume	2006

Other

Other	Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Country/Territory	Japan
City	Hakodate
Period	8/05/06 → 12/05/06

Keywords

Game theory
Multiagent learning

Access to Document

10.1145/1160633.1160775

Cite this

@inproceedings{bb432dfddc724657b058bd490d6c235e,

title = "RVσ(t): A unifying approach to performance and convergence in online multiagent learning",

abstract = "We present a new multiagent learning algorithm (RVσ(t)) that can guarantee both no-regret performance (all games) and policy convergence (some games of arbitrary size). Unlike its predecessor ReDVaLeR, it (1) does not need to distinguish whether its opponents are self-play or otherwise non-stationary, (2) is allowed to know its portion of any equilibrium that, we argue, leads to convergence in some games in addition to no-regret. Although the regret of RVσ(t) is analyzed in continuous time, we show that it grows slower than in other no-regret techniques like GIGA and GIGA-WoLF. We show that RVσ(t) can converge to coordinated behavior in coordination games, while GIGA, GIGA-WoLF may converge to poorly coordinated (mixed) behaviors.",

keywords = "Game theory, Multiagent learning",

author = "Bikramjit Banerjee and Jing Peng",

year = "2006",

doi = "10.1145/1160633.1160775",

language = "English",

isbn = "1595933034",

series = "Proceedings of the International Conference on Autonomous Agents",

pages = "798--800",

booktitle = "Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems",

note = "Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ; Conference date: 08-05-2006 Through 12-05-2006",

}

Banerjee, B & Peng, J 2006, RV_σ(t): A unifying approach to performance and convergence in online multiagent learning. in Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems. Proceedings of the International Conference on Autonomous Agents, vol. 2006, pp. 798-800, Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, Hakodate, Japan, 8/05/06. https://doi.org/10.1145/1160633.1160775

RV_σ(t): A unifying approach to performance and convergence in online multiagent learning. / Banerjee, Bikramjit; Peng, Jing.
Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems. 2006. p. 798-800 (Proceedings of the International Conference on Autonomous Agents; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - RVσ(t)

T2 - Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

AU - Banerjee, Bikramjit

AU - Peng, Jing

PY - 2006

Y1 - 2006

N2 - We present a new multiagent learning algorithm (RVσ(t)) that can guarantee both no-regret performance (all games) and policy convergence (some games of arbitrary size). Unlike its predecessor ReDVaLeR, it (1) does not need to distinguish whether its opponents are self-play or otherwise non-stationary, (2) is allowed to know its portion of any equilibrium that, we argue, leads to convergence in some games in addition to no-regret. Although the regret of RVσ(t) is analyzed in continuous time, we show that it grows slower than in other no-regret techniques like GIGA and GIGA-WoLF. We show that RVσ(t) can converge to coordinated behavior in coordination games, while GIGA, GIGA-WoLF may converge to poorly coordinated (mixed) behaviors.

AB - We present a new multiagent learning algorithm (RVσ(t)) that can guarantee both no-regret performance (all games) and policy convergence (some games of arbitrary size). Unlike its predecessor ReDVaLeR, it (1) does not need to distinguish whether its opponents are self-play or otherwise non-stationary, (2) is allowed to know its portion of any equilibrium that, we argue, leads to convergence in some games in addition to no-regret. Although the regret of RVσ(t) is analyzed in continuous time, we show that it grows slower than in other no-regret techniques like GIGA and GIGA-WoLF. We show that RVσ(t) can converge to coordinated behavior in coordination games, while GIGA, GIGA-WoLF may converge to poorly coordinated (mixed) behaviors.

KW - Game theory

KW - Multiagent learning

UR - http://www.scopus.com/inward/record.url?scp=34247189601&partnerID=8YFLogxK

U2 - 10.1145/1160633.1160775

DO - 10.1145/1160633.1160775

M3 - Conference contribution

AN - SCOPUS:34247189601

SN - 1595933034

SN - 9781595933034

T3 - Proceedings of the International Conference on Autonomous Agents

SP - 798

EP - 800

BT - Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems

Y2 - 8 May 2006 through 12 May 2006

ER -