Author name cluster

Fabio Panozzo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

AAAI Conference 2014 Conference Paper

Evolutionary Dynamics of Q-Learning over the Sequence Form

Fabio Panozzo
Nicola Gatti
Marcello Restelli

Multi–agent learning is a challenging open task in artificial intelligence. It is known an interesting connection between multi–agent learning algorithms and evolutionary game theory, showing that the learning dynamics of some algorithms can be modeled as replicator dynamics with a mutation term. Inspired by the recent sequence–form replicator dynamics, we develop a new version of the Q–learning algorithm working on the sequence form of an extensive–form game allowing thus an exponential reduction of the dynamics length w. r. t. those of the normal form. The dynamics of the proposed algorithm can be modeled by using the sequence– form replicator dynamics with a mutation term. We show that, although sequence–form and normal–form replicator dynamics are realization equivalent, the Q– learning algorithm applied to the two forms have non– realization equivalent dynamics. Originally from the previous works on evolutionary game theory models form multi–agent learning, we produce an experimental evaluation to show the accuracy of the model.

PDF Details

AAAI Conference 2013 Conference Paper

Efficient Evolutionary Dynamics with Extensive-Form Games

Nicola Gatti
Fabio Panozzo
Marcello Restelli

Evolutionary game theory combines game theory and dynamical systems and is customarily adopted to describe evolutionary dynamics in multi–agent systems. In particular, it has been proven to be a successful tool to describe multi–agent learning dynamics. To the best of our knowledge, we provide in this paper the first replicator dynamics applicable to the sequence form of an extensive–form game, allowing an exponential reduction of time and space w. r. t. the currently adopted replicator dynamics for normal form. Furthermore, our replicator dynamics is realization equivalent to the standard replicator dynamics for normal form. We prove our results for both discrete–time and continuous–time cases. Finally, we extend standard tools to study the stability of a strategy profile to our replicator dynamics.

PDF Details

AAMAS Conference 2013 Conference Paper

Extensive-form Games with Heterogeneous Populations

Nicola Gatti
Fabio Panozzo
Marcello Restelli

The adoption of Nash equilibrium (NE) in real–world settings is often impractical due to its too restrictive assumptions. Game theory and artificial intelligence provide alternative solution concepts. When knowledge about opponents utilities and types is not available, the appropriate solution concept for extensive–form games is the self–confirming equilibrium (SCE), which relaxes NE allowing agents to have incorrect beliefs off the equilibrium path. In this paper, we extend SCEs to capture situations in which a two–agent extensive–form game is played by heterogeneous populations of individuals that repeatedly match (e. g. , eBay).

PDF

AAAI Conference 2012 Conference Paper

Computing Equilibria with Two-Player Zero-Sum Continuous Stochastic Games with Switching Controller

Guido Bonomi
Nicola Gatti
Fabio Panozzo
Marcello Restelli

Equilibrium computation with continuous games is currently a challenging open task in artificial intelligence. In this paper, we design an iterative algorithm that finds an –approximate Markov perfect equilibrium with two–player zero–sum continuous stochastic games with switching controller. When the game is polynomial (i. e. , utility and state transitions are polynomial functions), our algorithm converges to = 0 by exploiting semidefinite programming. When the game is not polynomial, the algorithm exploits polynomial approximations and converges to an value whose upper bound is a function of the maximum approximation error with infinity norm. To our knowledge, this is the first algorithm for equilibrium approximation with arbitrary utility and transition functions providing theoretical guarantees. The algorithm is also empirically evaluated.

PDF Details

AAMAS Conference 2012 Conference Paper

Game theoretical solution concepts for learning agents with extensive-form games

Fabio Panozzo

My Ph. D thesis focuses on the study of solution concepts for rational learning agents in extensive-form games in absence of common knowledge; specifically, on the definition of solution concepts, their search, analysis of static and dynamic property, characterization of learning dynamics. Summarily, my work is finalized to better understand how to integrate more thoroughly game theory and machine learning.

PDF

AAMAS Conference 2012 Conference Paper

New Results on the Verification of Nash Refinements for Extensive-Form Games

Nicola Gatti
Fabio Panozzo

The computational study of strategic interactions situations has recently deserved a lot of attention in multi-agent systems. A number of results on strategic-form games and zero-sum extensive-form games are known in the literature, while general-sum extensive-form games are not studied in depth. We focus on the problem to decide whether or not a solution is a refinement of the Nash equilibrium (NE) for extensive-form games. Refinements are needed because the NE concept is not satisfactory for this game class. While verifying whether a solution is an NE is in $\mathcal{P}$, verifying whether it is a NE refinement may be not (all the results known so far show $\mathcal{NP}$-hardness). In this paper, we provide the first positive result, showing that verifying a \emph{sequential equilibrium} with any number of agents and a \emph{quasi perfect equilibrium} with two agents are in $\mathcal{P}$. We show also that when the input is expressed in (non-perturbed) sequence form even the problem to verify a subgame perfect equilibrium is $\mathcal{NP}$-complete and that sequence form, if applicable, must be rethought to verify (and therefore to compute) an extensive-form perfect equilibrium.

PDF

AAMAS Conference 2011 Conference Paper

Computing a Self-Confirming Equilibrium in Two-Player Extensive-Form Games

Nicola Gatti
Fabio Panozzo
Sofia Ceppi

The Nash equilibrium is the most commonly adopted solution concept for non-cooperative interaction situations. However, it underlays on the assumption of common information that is hardly verified in many practical situations. When information is not common, the appropriate game theoretic solution concept is the self-confirming equilibrium. It requires that every agent plays the best response to her beliefs and that the beliefs are correct on the equilibrium path. We present, to the best of our knowledge, the first study on the computation of a self-confirming equilibrium for two-player extensive-form games. We provide algorithms, we analyze the computational complexity, and we experimentally evaluate the performance of our algorithms in terms of computational time.

PDF