Regret Minimization

The formal measure of performance loss over a time horizon T. It is defined as the difference between the total reward accumulated by an optimal oracle strategy (which knows the best action in hindsight) and the total reward accumulated by the learning algorithm.

• Formula: R(T) = Σᵗ₌₁ᵀ (μ* - μ_{a_t}), where μ* is the mean reward of the optimal arm and μ_{a_t} is the reward of the chosen arm at time t.
• The goal is to achieve sublinear regret, meaning the average regret per round tends to zero as T → ∞.
• This proves the algorithm is learning and will eventually match the oracle's performance.

The central tension that drives regret accumulation. Exploitation selects the action currently believed to be best to maximize immediate reward, while exploration selects suboptimal actions to gather information and reduce uncertainty.

• Pure exploitation risks linear regret if the initial estimate is wrong and a superior action is never discovered.
• Pure exploration incurs constant opportunity cost by repeatedly testing known poor options.
• Regret-minimizing algorithms like Upper Confidence Bound (UCB) and Thompson Sampling mathematically balance this tradeoff to achieve logarithmic regret bounds.

The comparator benchmark against which regret is measured. The optimal oracle represents a theoretical agent with perfect knowledge of all reward distributions, selecting the single best fixed action in hindsight.

• In stochastic bandits, the oracle always pulls the arm with the highest true mean reward.
• In adversarial bandits, the oracle can choose the best fixed action in retrospect after seeing the full sequence of losses.
• This framework ensures the algorithm is judged against the strongest possible baseline, making regret a rigorous and unforgiving metric of learning efficiency.

A key characteristic of a sound algorithm is a provable upper bound on its cumulative regret. These bounds are typically expressed as a function of the number of arms K and the time horizon T.

• Problem-dependent bounds: O(log T) regret is achievable when there is a gap between the best and second-best arm (e.g., UCB achieves O(K log T / Δ)).
• Problem-independent bounds: O(√T) regret is the minimax optimal rate for adversarial settings (e.g., Exp3 algorithm).
• These theoretical guarantees provide robustness assurances to engineers deploying these models in production, confirming the algorithm will not diverge.

Extends the framework to settings where side information (context) is available before each decision. The oracle is now a policy that maps contexts to actions, and regret measures the gap to the best fixed policy in a hypothesis class.

• Used extensively in personalization engines where user features (device, location, history) inform the action choice.
• Algorithms like LinUCB and Contextual Thompson Sampling model the reward as a linear function of context features.
• Minimizing contextual regret ensures the system learns the optimal personalization strategy without requiring a pre-existing labeled dataset of perfect decisions.

Advanced regret notions that provide stronger behavioral guarantees. Swap regret measures the loss compared to any strategy that systematically swaps one action for another, while internal regret focuses on pairwise action modifications.

• An algorithm with no swap regret converges to a Correlated Equilibrium in multi-agent game theory settings.
• This is critical for multi-agent orchestration where independent learners must reach stable, self-enforcing conventions without central coordination.
• Algorithms achieving no internal regret ensure that, in hindsight, no single action substitution would have significantly improved the outcome.

A reinforcement learning algorithm that selects actions based on contextual information (user features, time of day, device type) to maximize cumulative rewards. Unlike simple multi-armed bandits, contextual bandits leverage side information to personalize decisions. The algorithm continuously balances exploration of uncertain options with exploitation of known high-reward actions. In practice, this powers real-time recommendation systems where the 'arms' are product offers and the 'context' is the user's current browsing session.

The fundamental dilemma in online learning systems: should the agent exploit known high-reward actions to maximize immediate gain, or explore uncertain options to gather information that may yield higher future rewards? Regret minimization provides a mathematical framework for quantifying the cost of this tradeoff. Key strategies include:

• Epsilon-greedy: Explore randomly with probability ε, exploit otherwise
• Upper Confidence Bound (UCB): Select arms based on optimistic estimates of their potential
• Thompson Sampling: Choose actions according to their posterior probability of being optimal

A Bayesian algorithm that addresses the exploration-exploitation dilemma by maintaining a posterior distribution over each action's expected reward. At each decision point, the algorithm samples from these distributions and selects the action with the highest sampled value. This naturally balances exploration—actions with high uncertainty have wider distributions and are more likely to produce high samples. Thompson Sampling achieves logarithmic regret in many settings and is widely deployed in production systems for its robustness and ease of implementation.

A mathematical framework for modeling sequential decision-making under uncertainty, defined by five components:

• States (S): All possible situations the agent can be in
• Actions (A): All possible decisions available to the agent
• Transition probabilities (P): The probability of moving from one state to another given an action
• Reward function (R): The immediate feedback signal received after taking an action
• Discount factor (γ): How much future rewards are valued relative to immediate ones MDPs provide the formal structure for computing optimal policies that minimize long-term regret.

A set of statistical techniques for estimating the performance of a new target policy using only historical data collected by a different, often suboptimal behavior policy. This is critical for regret minimization because deploying untested policies in production can incur real business costs. Key methods include:

• Inverse Propensity Scoring (IPS): Re-weights observed outcomes by the inverse probability of the action being taken
• Doubly Robust Estimation: Combines IPS with a direct outcome model for unbiased estimates even when one component is misspecified
• Direct Method (DM): Learns a reward predictor from logged data and evaluates the target policy against it

A deterministic algorithm for the multi-armed bandit problem that selects actions based on an optimistic estimate of their potential reward. For each arm, UCB computes an upper confidence bound: the empirical mean reward plus an exploration bonus that grows with uncertainty. The algorithm provably achieves sublinear regret with a logarithmic dependence on time. The UCB framework extends naturally to contextual settings (LinUCB) and tree search (UCT), making it foundational for regret-minimizing decision systems in production.