Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games
Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. One type of subrationality that describes human behavior well is the quantal response. While there exist algorithms for computing solutions against quantal opponents, they either do not scale or may provide strategies that are even worse than the entirely-rational Nash strategies. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games. Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard; (3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worst-case perfectly-rational opponent.
Code (0)
등록된 구현이 없습니다.
Tasks
counterfactualSimilar Papers 제목 키워드 기반
Actions Speak What You Want: Provably Sample-Efficient Reinforcement Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks
We study reinforcement learning (RL) for learning a Quantal Stackelberg Equilibrium (QSE) in an episodic Markov game with a leader-follower structure. In specific, at the outset of the game, the leader announces her poli…
Decision MakingLEMMAReinforcement Learning (RL)Safe Opponent-Exploitation Subgame Refinement
Search algorithms have been playing a vital role in the success of superhuman AI in both perfect information and imperfect information games. Specifically, search algorithms can generate a refinement of Nash equilibrium …
Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits
An ideal strategy in zero-sum games should not only grant the player an average reward no less than the value of Nash equilibrium, but also exploit the (adaptive) opponents when they are suboptimal. While most existing w…
From Behavioral Theories to Econometrics: Inferring Preferences of Human Agents from Data on Repeated Interactions
We consider the problem of estimating preferences of human agents from data of strategic systems where the agents repeatedly interact. Recently, it was demonstrated that a new estimation method called "quantal regret" pr…
EconometricsThe Focal Quantal Response Equilibrium
We propose a generalization of Quantal Response Equilibrium (QRE) built on a simple premise: some actions are more focal than others. In our model, which we call the Focal Quantal Response Equilibrium (Focal QRE), each p…