Markov chain entropy games and the geometry of their Nash equilibria
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908528918134784 |
|---|---|
| author | Choi, Michael C. H. Wolfer, Geoffrey |
| author_facet | Choi, Michael C. H. Wolfer, Geoffrey |
| contents | We introduce and study a two-player zero-sum game between a probabilist and Nature defined by a convex function $f$, a finite collection $\mathcal{B}$ of Markov generators (or its convex hull), and a target distribution $π$. The probabilist selects a mixed strategy $μ\in \mathcal{P}(\mathcal{B})$, the set of probability measures on $\mathcal{B}$, while Nature adopts a pure strategy and selects a $π$-reversible Markov generator $M$. The probabilist receives a payoff equal to the $f$-divergence $D_f(M \| L)$, where $L$ is drawn according to $μ$. We prove that this game always admits a mixed strategy Nash equilibrium and satisfies a minimax identity. In contrast, a pure strategy equilibrium may fail to exist. We develop a projected subgradient method to compute approximate mixed strategy equilibria with provable convergence guarantees. Connections to information centroids, Chebyshev centers, and Bayes risk are discussed. This paper extends earlier minimax results on $f$-divergences to the context of Markov generators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_04115 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Markov chain entropy games and the geometry of their Nash equilibria Choi, Michael C. H. Wolfer, Geoffrey Probability Information Theory Optimization and Control Computation 49J35, 60J27, 60J28, 62B10, 62C20, 90C47, 91A05, 91A68, 94A17, 94A29 We introduce and study a two-player zero-sum game between a probabilist and Nature defined by a convex function $f$, a finite collection $\mathcal{B}$ of Markov generators (or its convex hull), and a target distribution $π$. The probabilist selects a mixed strategy $μ\in \mathcal{P}(\mathcal{B})$, the set of probability measures on $\mathcal{B}$, while Nature adopts a pure strategy and selects a $π$-reversible Markov generator $M$. The probabilist receives a payoff equal to the $f$-divergence $D_f(M \| L)$, where $L$ is drawn according to $μ$. We prove that this game always admits a mixed strategy Nash equilibrium and satisfies a minimax identity. In contrast, a pure strategy equilibrium may fail to exist. We develop a projected subgradient method to compute approximate mixed strategy equilibria with provable convergence guarantees. Connections to information centroids, Chebyshev centers, and Bayes risk are discussed. This paper extends earlier minimax results on $f$-divergences to the context of Markov generators. |
| title | Markov chain entropy games and the geometry of their Nash equilibria |
| topic | Probability Information Theory Optimization and Control Computation 49J35, 60J27, 60J28, 62B10, 62C20, 90C47, 91A05, 91A68, 94A17, 94A29 |
| url | https://arxiv.org/abs/2310.04115 |