Is Bayesian regret always cumulative?

It is often cumulative over a horizon, but discounted or other variants exist and should be named.

Can it be measured directly from one live run?

Usually not exactly, because counterfactual rewards and the best informed policy are not fully observed.

Is it related to Thompson sampling?

Yes. Bayesian regret is commonly used in analyses of posterior-sampling policies.

AI Glossary / AI and machine learning / Advanced

Bayesian regret

Definition

Bayesian regret is expected regret averaged over a prior distribution of possible environments or unknown parameters. In sequential decision problems, it measures the expected cumulative reward shortfall of a learning policy compared with a benchmark that knows the relevant environment.

What it means

A learning system often has to choose before it knows which option is best. Trying an uncertain option may sacrifice immediate reward while providing information for later decisions. Regret measures the cost of those imperfect choices relative to a specified benchmark.

The Bayesian version averages that cost over the uncertainty represented by a prior. This differs from reporting regret for one fixed environment or the worst case over all environments. The averaging distribution is therefore part of the meaning of the result.

For business readers, the concept helps discuss exploration costs. It is not emotional regret and does not directly measure every business risk. A low average reward shortfall can coexist with undesirable outcomes in particular situations.

How it works

Specify the environment model, available actions, reward function and decision horizon. For each possible environment, define the benchmark, commonly an optimal action or policy with knowledge unavailable to the learner.

Regret accumulates the difference between the benchmark's expected reward and the learner's expected reward over decisions. Bayesian regret then takes an expectation over the prior on environments, as well as relevant randomness in observations or the policy.

Research uses the measure to analyze methods such as posterior sampling. Practical estimates may rely on simulation because the true best action is unknown in live operation. The prior, reward and horizon should match the question being studied. A theoretical bound applies under its stated assumptions, not automatically to any production recommender or experiment.

Three practical examples

A research team compares bandit policies across simulated environments drawn from a specified prior.
An online-testing team studies the expected reward cost of learning which option performs best.
A technical reviewer distinguishes an average Bayesian regret claim from a worst-case guarantee.

Think of it this way

Think of choosing among unfamiliar routes to work. Trying a route that turns out slower can cost time now but teach something useful for future trips. Regret compares those trips with knowing the best route beforehand.

The analogy is limited because formal analysis needs a defined model of changing conditions and rewards. The Bayesian average also depends on how the possible route conditions were weighted initially.

Worked example

Averaging regret across environments

Consider a teaching model with two possible environments. The prior gives environment A probability 0.7 and environment B probability 0.3. Over a fixed horizon, a policy's expected cumulative regret is 10 reward units in A and 30 in B.

Its Bayesian regret is 0.7 × 10 + 0.3 × 30 = 16 reward units. Its worst-case regret among these two environments is 30, not 16.

If the prior instead assigned equal probability to both, the Bayesian average would be 20. The policy itself need not change for the evaluation average to change, although a Bayesian policy might also depend on the prior. This example isolates why the averaging distribution must accompany the reported number.

Illustrative case study

A fictional digital-learning company tests policies for selecting practice exercises. In simulation, one policy has low Bayesian regret under a model that assumes most learners resemble a common profile. Reviewers ask how it performs on less common profiles.

The team reports the average and subgroup behavior separately, checks alternative prior mixtures and includes constraints on unsuitable exercise choices. It also examines whether the simulated reward corresponds to learning rather than simply clicks.

The case illustrates the limits of one summary measure. A favorable Bayesian average is useful evidence about the stated model, but does not replace broader evaluation of the service.

Common misconceptions and mistakes

Bayesian regret is the worst possible loss. It averages under a prior rather than necessarily taking a worst case.
Zero observed failure means zero regret. The benchmark may obtain better expected reward even when no obvious failure occurs.
A regret bound guarantees business success. The result depends on the reward, model, horizon and assumptions.

Business use

Bayesian regret is useful when evaluating learning policies that balance exploration and exploitation. It gives a language for the expected opportunity cost of learning under uncertainty.

Ask what the benchmark knows, how environments are weighted and which reward is counted. Include hard constraints separately from reward optimization. For deployment, inspect uncommon but consequential cases and test sensitivity to the prior. A theoretical performance measure should clarify the trade-off, not hide who bears the cost of exploration.

Check your understanding

Expected regrets are 10 and 30 with prior weights 0.7 and 0.3. Is the Bayesian regret 30?

Answer: No. It is 16. Thirty is the largest of the two environment-specific values.

Related terms

Regret
Thompson sampling
Prior distribution
Policy
multi-armed bandit
exploration–exploitation
expected reward

Learn next

Read multi-armed bandit and expected reward. Compare a policy's average result with its results in separate environments, and state the assumptions used to weight those environments.

Policy

Sources

Daniel Russo and Benjamin Van Roy, Learning to Optimize via Posterior Sampling: https://arxiv.org/abs/1301.2609. Russo and colleagues, A Tutorial on Thompson Sampling: https://arxiv.org/abs/1707.02038. Primary research and an author-written tutorial discuss Bayesian regret. All numerical values and the learning-company scenario are original illustrations.

Previous: Bayesian Regression Next: Bayesian reinforcement learning