Learning the Expected Core of Strictly Convex Stochastic Cooperative Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916461633601536 |
|---|---|
| author | Tran, Nam Phuong Ta, The Anh Shi, Shuqing Mandal, Debmalya Du, Yali Tran-Thanh, Long |
| author_facet | Tran, Nam Phuong Ta, The Anh Shi, Shuqing Mandal, Debmalya Du, Yali Tran-Thanh, Long |
| contents | Reward allocation, also known as the credit assignment problem, has been an important topic in economics, engineering, and machine learning. An important concept in reward allocation is the core, which is the set of stable allocations where no agent has the motivation to deviate from the grand coalition. In previous works, computing the core requires either knowledge of the reward function in deterministic games or the reward distribution in stochastic games. However, this is unrealistic, as the reward function or distribution is often only partially known and may be subject to uncertainty. In this paper, we consider the core learning problem in stochastic cooperative games, where the reward distribution is unknown. Our goal is to learn the expected core, that is, the set of allocations that are stable in expectation, given an oracle that returns a stochastic reward for an enquired coalition each round. Within the class of strictly convex games, we present an algorithm named \texttt{Common-Points-Picking} that returns a point in the expected core given a polynomial number of samples, with high probability. To analyse the algorithm, we develop a new extension of the separation hyperplane theorem for multiple convex sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07067 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning the Expected Core of Strictly Convex Stochastic Cooperative Games Tran, Nam Phuong Ta, The Anh Shi, Shuqing Mandal, Debmalya Du, Yali Tran-Thanh, Long Computer Science and Game Theory Machine Learning Reward allocation, also known as the credit assignment problem, has been an important topic in economics, engineering, and machine learning. An important concept in reward allocation is the core, which is the set of stable allocations where no agent has the motivation to deviate from the grand coalition. In previous works, computing the core requires either knowledge of the reward function in deterministic games or the reward distribution in stochastic games. However, this is unrealistic, as the reward function or distribution is often only partially known and may be subject to uncertainty. In this paper, we consider the core learning problem in stochastic cooperative games, where the reward distribution is unknown. Our goal is to learn the expected core, that is, the set of allocations that are stable in expectation, given an oracle that returns a stochastic reward for an enquired coalition each round. Within the class of strictly convex games, we present an algorithm named \texttt{Common-Points-Picking} that returns a point in the expected core given a polynomial number of samples, with high probability. To analyse the algorithm, we develop a new extension of the separation hyperplane theorem for multiple convex sets. |
| title | Learning the Expected Core of Strictly Convex Stochastic Cooperative Games |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2402.07067 |