In sequential decision-making, the standard way to measure performance is regret: the difference between the rewards an agent actually collected and the rewards it could have collected had it known the best action from the start.
Traditional frequentist analysis often treats regret as a function of the environment's complexity—for example, the number of possible actions or the dimensionality of the state space. However, this "worst-case" view ignores a crucial factor: what the agent already knows. If an agent starts with a highly accurate prior belief, it should logically perform better than an agent starting from scratch.
A growing body of research has formalized this intuition using information theory, proving that regret is not just a property of the environment, but a direct consequence of the agent's initial uncertainty.
The Information Ratio and the Cost of Learning
The bridge between information and performance was solidified by Daniel Russo and Benjamin Van Roy in An Information-Theoretic Analysis of Thompson Sampling. They introduced the Information Ratio, a metric that relates the expected regret in a single step to the information gained about which action is optimal.
The core insight is that an agent only incurs regret when it chooses an action that provides information. By defining regret in terms of the Shannon entropy of the optimal action distribution, they showed that agents with strong prior beliefs experience lower cumulative regret. Instead of scaling with the total number of actions, the performance bounds scale with the agent's internal uncertainty. This framework was later extended to complex reinforcement learning environments in Information-Theoretic Confidence Bounds for Reinforcement Learning, linking mutual information to the classic exploration-exploitation tradeoff.
Quantifying the Exchange Rate of Bits
If regret is the cost of acquiring information, what is the "exchange rate"? Itai Shufaro, Nadav Merlis, and colleagues addressed this in On Bits and Bandits: Quantifying the Regret-Information Trade-off. By applying Fano’s inequality, they established that the initial uncertainty (measured in bits) sets a fundamental theoretical limit on the minimum regret an agent will encounter.
This perspective transforms the search for optimal actions into a search for information. In A Bayesian Approach to Online Planning, Nir Greshler and others demonstrated that in tree-search algorithms like those used in AlphaZero, search regret is directly proportional to the entropy of the prior distribution. "Knowing what you don't know" allows the agent to focus its computational budget on the most informative branches of the search tree.
The Geometry of Prior Knowledge
While entropy provides a broad measure of uncertainty, the structure of that uncertainty also matters. In linear problems, uncertainty is often represented as a confidence ellipsoid. Yingru Li and Zhi-Quan Luo showed in Prior-dependent analysis of posterior sampling reinforcement learning with function approximation that regret bounds can be tightened by accounting for the log-determinant of the prior covariance matrix. This "prior-dependent" analysis removes inefficiencies found in frequentist benchmarks, proving that a "sharp" prior narrows the search space from the very first step.
Interestingly, the cost of a vague prior isn't always catastrophic. Yifan Zhu, John Duchi, and Benjamin Van Roy discovered in Prior Diffusiveness and Regret in the Linear-Gaussian Bandit that the "burn-in" phase—the initial period where an agent learns from a vague prior—adds a fixed, additive cost to regret rather than a multiplicative one. This explains why Thompson Sampling performs so well in practice even when the initial prior is uninformative.
Learning the Prior through Meta-Learning
If performance is so dependent on the quality of the prior, can we learn the prior itself? This is the motivation behind Meta-Thompson Sampling. Branislav Kveton and his co-authors in Meta-Thompson Sampling developed a framework where an agent interacts with a series of related tasks to discover the underlying distribution of rewards.
As the agent refines and concentrates its learned prior, the regret incurred on subsequent tasks decreases. Elynn Y. Chen extended this in Prior-Aligned Meta-RL, using a change-of-measure argument to bound the performance gap between an agent using a learned prior and an "oracle" that already knows the true distribution.
Adaptation and Efficiency
Finally, modern Bayesian algorithms are becoming increasingly adaptive to the type of uncertainty they encounter. Aadirupa Saha and Branislav Kveton introduced VarTS in Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling, which learns reward variances alongside means. The philosophy here is simple: an agent should only "pay" in regret for the parameters it is actually uncertain about.
By bridging frequentist instance-dependent analysis with Bayesian integration, researchers like Alexia Atsidakou have even achieved Finite-Time Logarithmic Bayes Regret Upper Bounds. These bounds explicitly capture the mathematical value of prior information, proving that as the prior becomes more concentrated, the cost of exploration can approach a constant value.