Gaussian-Dirichlet Posterior Dominance in Sequential Learning

Ian Osband, Benjamin Van RoyarXiv 2017 · arXiv

Abstract

This paper establishes a formal mathematical proof that for categorical data, a Dirichlet posterior distribution second-order stochastically dominates (SSD) a Gaussian approximation. This result implies that the Dirichlet model is inherently less "risky" or spread out while maintaining the same mean. This theoretical bridge justifies the use of Dirichlet-based models in sequential learning and reinforcement learning (RL), where accurate "stochastic optimism" is essential for efficient exploration.

Introduction

In sequential learning and reinforcement learning, agents must continuously update their beliefs based on categorical observations, such as binary rewards. While the Dirichlet distribution is the conjugate prior for such data, Gaussian models are frequently employed due to their mathematical tractability. This paper investigates the theoretical implications of this approximation, proving that the Dirichlet model is more concentrated and less prone to extreme variance than its Gaussian counterpart when matched on the same data.

Theoretical Framework: Stochastic Dominance

The authors utilize the framework of second-order stochastic dominance (SSD) to compare the two distributions. SSD is a powerful tool for relating the "spread" of distributions. If a random variable $X$ dominates $Y$ via SSD, then for any concave utility function—representing a risk-averse agent—the expected utility of $X$ is higher than that of $Y$. This indicates that $X$ is less risky than $Y$, despite having the same mean.

Comparison of Cumulative Distribution Functions (CDFs) illustrating second-order stochastic dominance (SSD) as a more nuanced metric than first-order dominance for distributions with equal means.

Methodology

The proof of Dirichlet-Gaussian dominance is derived analytically through a two-step process:

  1. Dirichlet vs. Beta: The Dirichlet distribution is shown to be a mean-preserving spread of a specific Beta distribution.
  2. Beta vs. Gaussian: The authors prove that this Beta distribution "single-crossing dominates" the Gaussian distribution, which implies SSD.

The proof for the second step is particularly intensive, requiring the subdivision of the $(\alpha, \beta)$ parameter space into three distinct regions ($R1, R2, R3$). By applying calculus and the mean value theorem, the authors demonstrate that the probability density functions (PDFs) cross at most twice, satisfying the single-crossing condition.

Subdivision of the parameter space into regions R1, R2, and R3, used to prove that the Beta distribution single-crossing dominates the Gaussian distribution.

Key Results

The central result, Theorem 1, establishes that if $X$ is a Dirichlet posterior mean and $Y$ is a Gaussian posterior mean matched on the same data, then $E[X] = E[Y]$ and $X \succeq_{ssd} Y$.

Furthermore, Corollary 1 (the "Two Observation" Rule) guarantees that this dominance relationship holds as long as the total "prior plus data" count ($\sum \alpha_i$) is at least 2. This mild condition ensures the result's applicability in practical sequential learning scenarios. These findings provide a theoretical foundation for using Dirichlet-based models in RL, as they offer a more refined version of the optimism required for exploration compared to standard Gaussian noise.

Limitations and Future Work

The authors acknowledge the mathematical complexity of their proof and suggest that a more elegant method might exist. Additionally, the study focuses exclusively on the Dirichlet-Gaussian relationship. Future work could explore whether similar dominance results hold for other common Bayesian distributions, such as Gamma or Poisson. While the theory is robust, empirical measurement of performance gains in live RL systems remains an open area for research.

Summary updated

Abstract

We consider the problem of sequential learning from categorical observations bounded in [0,1]. We establish an ordering between the Dirichlet posterior over categorical outcomes and a Gaussian posterior under observations with N(0,1) noise. We establish that, conditioned upon identical data with at least two observations, the posterior mean of the categorical distribution will always second-order stochastically dominate the posterior mean of the Gaussian distribution. These results provide a useful tool for the analysis of sequential learning under categorical outcomes.
BibTeX
@misc{osband2017gaussian,
  author = {Ian Osband and Benjamin Van Roy},
  title = {{Gaussian-Dirichlet Posterior Dominance in Sequential Learning}},
  year = {2017},
  eprint = {1702.04126},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.04126},
}
Figure