Markov chain entropy games and the geometry of their Nash equilibria

Abstract

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 $\pi$. The probabilist selects a mixed strategy $\mu \in \mathcal{P}(\mathcal{B})$, the set of probability measures on $\mathcal{B}$, while Nature adopts a pure strategy and selects a $\pi$-reversible Markov generator $M$. The probabilist receives a payoff equal to the $f$-divergence $D_f(M\Vert L)$, where $L$ is drawn according to $\mu$. 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.

arXiv comment29 pages, 2 figures

References in corpus (7)

• Rényi Divergence and Kullback-Leibler Divergence
• Accelerating diffusions
• Non-reversible Metropolis-Hastings
• Improving the convergence of reversible samplers
• Metropolis-Hastings reversiblizations of non-reversible Markov chains
• Systematic approaches to generate reversiblizations of Markov chains
• On hitting time, mixing time and geometric interpretations of Metropolis-Hastings reversiblizations