Bayesian Learning In Episodic Zero-sum Games

Abstract

We study Bayesian learning in episodic, finite-horizon zero-sum Markov games with unknown transition and reward models. We investigate a posterior algorithm in which each player maintains a Bayesian posterior over the game model, independently samples a game model at the beginning of each episode, and computes an equilibrium policy for the sampled model. We analyze two settings: (i) Both players use the posterior sampling algorithm, and (ii) Only one player uses posterior sampling while the opponent follows an arbitrary learning algorithm. In each setting, we provide guarantees on the expected regret of the posterior sampling agent. Our notion of regret compares the expected total reward of the learning agent against the expected total reward under equilibrium policies of the true game. Our main theoretical result is an expected regret bound for the posterior sampling agent of order \(O(HS\sqrt\{ABHKlog(SABHK)\})\) where \(K\) is the number of episodes, \(H\) is the episode length, \(S

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyueh2026bayesian

Related papers

• A Bayesian Learning Algorithm For Unknown Zero-sum Stochastic Games With An Arbitrary Opponent (2021)0.00
• Efficient Episodic Learning Of Nonstationary And Unknown Zero-sum Games Using Expert Game Ensembles (2021)3.58
• Online Learning In Unknown Markov Games (2020)0.00
• Improving Sample Efficiency Of Model-free Algorithms For Zero-sum Markov Games (2023)0.00
• Model-based Reinforcement Learning For Offline Zero-sum Markov Games (2022)0.00
• Learning Two-player Mixture Markov Games: Kernel Function Approximation And Correlated Equilibrium (2022)0.00
• Model-free Learning For Two-player Zero-sum Partially Observable Markov Games With Perfect Recall (2021)0.00
• Decentralized Model-free Reinforcement Learning In Stochastic Games With Average-reward Objective (2023)0.00