Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSound Algorithms in Imperfect Information Games
80
0
0.0
(
0
)
Added by
Michal Sustr
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Search has played a fundamental role in computer game research since the very beginning. And while online search has been commonly used in perfect information games such as Chess and Go, online search methods for imperfect information games have only been introduced relatively recently. This paper addresses the question of what is a sound online algorithm in an imperfect information setting of two-player zero-sum games. We argue that the~fixed-strategy~definitions of exploitability and $epsilon$-Nash equilibria are ill-suited to measure an online algorithms worst-case performance. We thus formalize $epsilon$-soundness, a concept that connects the worst-case performance of an online algorithm to the performance of an $epsilon$-Nash equilibrium. As $epsilon$-soundness can be difficult to compute in general, we introduce a consistency framework -- a hierarchy that connects an online algorithms behavior to a Nash equilibrium. These multiple levels of consistency describe in what sense an online algorithm plays just like a fixed Nash equilibrium. These notions further illustrate the difference between perfect and imperfect information settings, as the same consistency guarantees have different worst-case online performance in perfect and imperfect information games. The definitions of soundness and the consistency hierarchy finally provide appropriate tools to analyze online algorithms in repeated imperfect information games. We thus inspect some of the previous online algorithms in a new light, bringing new insights into their worst-case performance guarantees.
rate research
Read More
The combination of deep reinforcement learning and search at both training and test time is a powerful paradigm that has led to a number of successes in single-agent settings and perfect-information games, best exemplified by AlphaZero. However, prior algorithms of this form cannot cope with imperfect-information games. This paper presents ReBeL, a general framework for self-play reinforcement learning and search that provably converges to a Nash equilibrium in any two-player zero-sum game. In the simpler setting of perfect-information games, ReBeL reduces to an algorithm similar to AlphaZero. Results in two different imperfect-information games show ReBeL converges to an approximate Nash equilibrium. We also show ReBeL achieves superhuman performance in heads-up no-limit Texas holdem poker, while using far less domain knowledge than any prior poker AI.
Counterfactual Regret Minimization (CFR) is an efficient no-regret learning algorithm for decision problems modeled as extensive games. CFRs regret bounds depend on the requirement of perfect recall: players always remember information that was revealed to them and the order in which it was revealed. In games without perfect recall, however, CFRs guarantees do not apply. In this paper, we present the first regret bound for CFR when applied to a general class of games with imperfect recall. In addition, we show that CFR applied to any abstraction belonging to our general class results in a regret bound not just for the abstract game, but for the full game as well. We verify our theory and show how imperfect recall can be used to trade a small increase in regret for a significant reduction in memory in three domains: die-roll poker, phantom tic-tac-toe, and Bluff.
We define the notion of Bayes correlated Wardrop equilibrium for general nonatomic games with anonymous players and incomplete information. Bayes correlated Wardrop equilibria describe the set of equilibrium outcomes when a mediator, such as a traffic information system, provides information to the players. We relate this notion to Bayes Wardrop equilibrium. Then, we provide conditions -- existence of a convex potential and complete information -- under which mediation does not improve equilibrium outcomes. We then study full implementation and, finally, information design in anonymous games with a finite set of players, when the number of players tends to infinity.
In some games, additional information hurts a player, e.g., in games with first-mover advantage, the second-mover is hurt by seeing the first-movers move. What properties of a game determine whether it has such negative value of information for a particular player? Can a game have negative value of information for all players? To answer such questions, we generalize the definition of marginal utility of a good to define the marginal utility of a parameter vector specifying a game. So rather than analyze the global structure of the relationship between a games parameter vector and player behavior, as in previous work, we focus on the local structure of that relationship. This allows us to prove that generically, every game can have negative marginal value of information, unless one imposes a priori constraints on allowed changes to the games parameter vector. We demonstrate these and related results numerically, and discuss their implications.
We consider a game-theoretic model of information retrieval with strategic authors. We examine two different utility schemes: authors who aim at maximizing exposure and authors who want to maximize active selection of their content (i.e. the number of clicks). We introduce the study of author learning dynamics in such contexts. We prove that under the probability ranking principle (PRP), which forms the basis of the current state of the art ranking methods, any better-response learning dynamics converges to a pure Nash equilibrium. We also show that other ranking methods induce a strategic environment under which such a convergence may not occur.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
