| abstract | openreview | title | layout | series | publisher | issn | id | month | tex_title | firstpage | lastpage | page | order | cycles | bibtex_author | author | date | address | container-title | volume | genre | issued | extras | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
In this paper, we study a multi-agent bandit problem in an unknown general-sum game repeated for a number of rounds (i.e., learning in a black-box game with bandit feedback), where a set of agents have no information about the underlying game structure and cannot observe each other’s actions and rewards. In each round, each agent needs to play an arm (i.e., action) from a (possibly different) arm set (i.e., action set), and only receives the reward of the played arm that is affected by other agents’ actions. The objective of each agent is to minimize her own cumulative swap regret, where the swap regret is a generic performance measure for online learning algorithms. We are the first to give a near-optimal high-probability swap-regret upper bound based on a refined martingale analysis for the exponential-weighting-based algorithms with the implicit exploration technique, which can further bound the expected swap regret instead of the pseudo-regret studied in the literature. It is also guaranteed that correlated equilibria can be achieved in a polynomial number of rounds if the algorithm is played by all agents. Furthermore, we conduct numerical experiments to verify the performance of the studied algorithm. |
INf380Y5-v |
A near-optimal high-probability swap-Regret upper bound for multi-agent bandits in unknown general-sum games |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
huang23b |
0 |
A near-optimal high-probability swap-Regret upper bound for multi-agent bandits in unknown general-sum games |
911 |
921 |
911-921 |
911 |
false |
Huang, Zhiming and Pan, Jianping |
|
2023-07-02 |
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence |
216 |
inproceedings |
|
|