Optimal Regret Exponents for Bayesian Statistical Decision Problems
2026-06-08 • Information Theory
Information Theory
AI summaryⓘ
The authors studied decision-making problems where there are limited states and actions and uncertainty in which state is true. They found that the best way to minimize regret (wrong decisions) gets better really fast as you gather more data, and they precisely describe how fast using a mathematical quantity called the Chernoff information. Their results generalize known formulas from simpler cases like hypothesis testing and also provide new insights for list hypothesis testing. This helps us understand how quickly we can expect decision errors to shrink in these statistical problems.
Bayesian decision problemfinite-state systemsfinite-action systemsBayes regretChernoff informationhypothesis testinghypothesis exclusionerror exponentlist hypothesis testing
Authors
Hyun-Young Park, Si-Hyeon Lee
Abstract
We study finite-state finite-action Bayesian statistical decision problems. While exact error-exponent characterizations are known for several special cases, including hypothesis testing and hypothesis exclusion, the asymptotic behavior of the optimal Bayes regret is largely unknown for general decision problems. In this paper, we show that the optimal regret always decays exponentially fast and characterize its exact exponent for arbitrary loss functions. The exponent is given by the minimum multivariate Chernoff information over the minimal incompatible subsets of states, where an incompatible subset is a collection of states for which no single action is optimal for all states in the subset. Our result recovers the classical pairwise-minimum Chernoff exponent for symmetric multiple hypothesis testing and the multivariate Chernoff exponent for hypothesis exclusion, while also yielding, to the best of our knowledge, the first exact exponent characterization for list hypothesis testing.