Posterior Sampling for Competitive RL: Function Approximation and Partial Observation

This paper investigates posterior sampling algorithms for competitive reinforcement learning (RL) in the context of general function approximations. Focusing on zero-sum Markov games (MGs) under two critical settings, namely self-play and adversarial learning, we first propose the self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, capturing the exploration-exploitation trade-off in MGs. Based on self-play GEC, we propose a model-based self-play posterior sampling method to control both players to learn Nash equilibrium, which can successfully handle the partial observability of states. Furthermore, we identify a set of partially observable MG models fitting MG learning with the adversarial policies of the opponent. Incorporating the adversarial GEC, we propose a model-based posterior sampling method for learning adversarial MG with potential partial observability. We further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes $T$. To the best of our knowledge, we for the first time develop generic model-based posterior sampling algorithms for competitive RL that can be applied to a majority of tractable zero-sum MG classes in both fully observable and partially observable MGs with self-play and adversarial learning.

Paper

Similar papers

Peer review

Reviewer qywY5/10 · confidence 2/52023-07-02

Summary

The paper considers a zero-sum Markov game with unknown dynamics in the case of full and partial observations. The authors propose algorithms for finding a Nash equilibrium in the games, in which, at each iteration, virtual games with dynamics sampled from certain distributions are solved. The paper's main result is theoretical and consists of estimates for the rate of the algorithms' convergence.

Strengths

The paper is aimed at solving an important problem. It is well structured and written in clear mathematical language.

Weaknesses

Unfortunately, as a non-specialist, it is rather difficult for me to assess the significance of the obtained theoretical results. It is not entirely clear what useful conclusion the reader can draw from them concerning practical methods for solving zero-sum Markov games. The proposed algorithms seem very abstract since it is difficult to calculate the indicated distributions in experimental tasks. If I'm wrong and this is feasible, an example confirming this would significantly strengthen the paper. One more thing I doubt is the fact that in the algorithms, the authors apparently assume that a Nash equilibrium in Markov games exists. This is true if we consider games with an infinite horizon, but I'm not sure if this is true for games with a fixed number of steps $H$. Usually, in such games, it is assumed that the policy depends not only on the state but also on the step number. Otherwise, the existence of a Nash equilibrium is not obvious to me, and I would welcome a reference to this fact. The paper also contains typos: 178 - $V^*$ instead of $V_1^*$. 189 - $P^{\pi,\nu}_f$ instead of $P^{\pi,\nu}_h$ 246 - “begin” instead of “bening”

Questions

On line 151, the authors introduce the reward function $r_h(o,a,b)$. It seems a bit exotic that it depends on an observation $o$ rather than on a state $s$. Is it important for the obtained results?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The paper does not have potentially negative societal impact.

Reviewer DqQm7/10 · confidence 4/52023-07-06

Summary

This paper investigates posterior sampling algorithms for competitive reinforcement learning (RL) with general function approximations in zero-sum Markov games (MGs). It introduces complexity measures for function approximation and proposes model-based self-play and adversarial posterior sampling methods to learn Nash equilibrium in partially observable states. The algorithms provide low regret bounds and can be applied to various tractable zero-sum MG classes in both fully observable and partially observable settings.

Strengths

I think this work really pushes the Multiagent+PORL community research efforts further by answering: > can we design a generic posterior sampling algorithm for MGRL in the context of function approximation? The main contribution of model-based posterior sampling algorithm equipped with rigorous analyses is worthy for publication at NeurIPS.

Weaknesses

I have only minor weaknesses for this work as follows: 1. For the self-play, Algorithm 1 and 2 seems repetitive. One can essentially combine them for presentation. 2. More discussion needs to be added comparing between Self-play and Adversarial results (Thm 1 and 2). For example, the self-play considered here is the zero-sum, hence the player 2 is the worst possible adversary. With this notion, comparing these two results will be helpful for future directions. It will be curious to see if the main player in Self-play (Thm 1 result) can handle the adversary in the Alg 3.

Questions

na

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

na

Reviewer pkbQ5/10 · confidence 1/52023-07-06

Summary

This paper focuses on posterior sampling for competitive reinforcement learning, aiming to propose a model-based self-play posterior sampling method to approximate Nash equilibrium in the case of self-play and adversarial learning. The theoretical analysis indicates that the proposed method achieves a low regret bound that can scale sublinearly converge.

Strengths

1. This paper is well-organized and gives a throughout survey of the related work. 2. this paper seems to be a solid theoretical work, though I'm not entirely sure of that.

Weaknesses

1. Too long a supplementary, so that the reviewer may miss some details

Questions

line 56: "... partial observations into the posterior sampling framework under a MARL ...", so the question is what is the difficulty of using posterior sampling in POMDP?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Reviewer Gu3i6/10 · confidence 3/52023-07-26

Summary

This paper investigates posterior sampling algorithms for competitive RL in the context of general function approximations. The authors propose the self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, capturing the exploration-exploitation trade-off in MGs. They further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes T.

Strengths

1. Two new generalized eluder coefficients are proposed as the complexity measure for the competitive RL with function approximation. 2. The authors also propose a novel model-based posterior sampling algorithm with self-play to learn the Nash equilibrium with provable regret bounds. 3. The technical contribution of the paper looks solid.

Weaknesses

Currently, readers are hard to follow the technical results in the main paper. It will be better if the author could include some explanatory parts for explaining the technical details intuitively, so as to highlight their technical contribution.

Questions

Please refer to the Weaknesses section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No.

Reviewer qywY2023-08-14

Comments on the response

Thanks to the authors for answering my questions. Considering them and the opinions of other reviewers, I am ready to raise my rating.

Authorsrebuttal2023-08-14

Thank you for raising the rating

Thank you for raising the rating! We greatly appreciate you taking the time to read our rebuttal and reconsider our work. We are happy to answer any further questions to address the remaining concerns regarding our submission.

Authorsrebuttal2023-08-19

We greatly appreciate you taking the time to read our rebuttal. We are happy to answer any further questions to address the remaining concerns regarding our submission.

Reviewer DqQm2023-08-20

The rebuttal addressed my concerns. My rating is unchanged considering the rebuttal and other reviewers’ concerns.

Authorsrebuttal2023-08-20

We greatly appreciate you taking the time to read our rebuttal. We are happy to answer any further questions to address the remaining concerns regarding our submission.

Authorsrebuttal2023-08-20

Dear Reviewer pkbQ, We sincerely appreciate you taking the time to thoroughly evaluate our paper and provide insightful questions. In our rebuttal, we aimed to carefully and comprehensively answer your questions. We sincerely hope our responses and clarifications can adequately alleviate your initial concerns about our work. For your concerns about the long supplementary material, since our work presents a novel RL algorithm with theoretical guarantees, we include rigorous proofs and analysis in the supplementary material to support our results. The detail in the supplementary material is necessary for a technically sound paper. We truly value the discussion period and hope to address any concerns to the best of our ability on the last day of this period. Please do not hesitate to let us know if there are any lingering concerns or unclearness in our rebuttal. We would be more than happy to address them.

Reviewer pkbQ2023-08-21

Thanks for your clarification

I thank the authors for their response and clarification, which further helps me understand your contribution. But I'll keep my score as it is hard to check the correctness of such long theoretical parts in such a short period.

Authorsrebuttal2023-08-21

We sincerely appreciate the reviewer taking the time to read through our rebuttal. We are pleased to know that our rebuttal was able to help resolve your questions. To enable readers to grasp our main proof ideas, we provided a proof sketch at the end of the main text. In our revision, we will ensure to further highlight our technical contributions by extracting additional important details from the supplement and incorporating them into the main text.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC