Markov chain entropy games and the geometry of their Nash equilibria

We introduce and study a two-player zero-sum game between a probabilist and Nature defined by a convex function f , a finite collection B of Markov generators (or its convex hull), and a target distribution .The probabilist selects a mixed strategy P(B), the set of probability measures on 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 such as (Haussler, 1997;Haussler and Opper, 1997;Gushchin and Zhdanov, 2006) to the context of Markov generators.