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

2 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
Volume	2006
DOIs	https://doi.org/10.1145/1160633.1160775
State	Published - 1 Dec 2006
Event	Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS - Hakodate, Japan Duration: 8 May 2006 → 12 May 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",

month = dec,

day = "1",

doi = "10.1145/1160633.1160775",

language = "English",

isbn = "1595933034",

volume = "2006",

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. 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

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/12/1

Y1 - 2006/12/1

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

VL - 2006

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 -