Regret Minimization

Regret is formally defined as the difference between the expected cumulative reward of always selecting the optimal arm and the expected cumulative reward accumulated by the algorithm over a time horizon T. It mathematically captures the cost of exploration. A sublinear regret bound, such as O(log T), proves the algorithm learns the optimal policy over time, as the average regret per round approaches zero.

The objective splits into two distinct metrics:

• Cumulative Regret: The total loss over the entire learning period. Minimizing this is the goal when rewards matter during exploration, such as in dynamic pricing.
• Simple Regret: The loss at the final decision point. Minimizing this is preferred in pure exploration settings, like identifying the best clinical trial arm, where intermediate rewards are irrelevant.

A bandit algorithm's theoretical guarantee is expressed as a regret bound. The Lai-Robbins lower bound proves that no algorithm can achieve a regret lower than O(log T) asymptotically for stochastic bandits. Algorithms like Upper Confidence Bound (UCB) and Thompson Sampling are considered optimal because they match this lower bound, proving they efficiently balance the exploration-exploitation trade-off.

In contextual bandits, regret is defined relative to the best hypothesis in a policy class, not just a single best arm. The algorithm observes a contextual feature vector x before deciding. Regret measures the loss compared to the optimal mapping from contexts to actions. Algorithms like LinUCB achieve regret bounds of Õ(√T) by assuming a linear relationship between context and reward.

The literature distinguishes between two formalizations:

• Expected Regret: The expectation over both the algorithm's randomization and the reward noise.
• Pseudo-Regret: Compares the algorithm's expected cumulative reward to the best fixed action in expectation. Pseudo-regret is a weaker but more tractable metric, commonly used to prove upper bounds for algorithms like Epsilon-Greedy.

In a non-stationary bandit, the optimal arm changes over time, making static regret meaningless. The objective shifts to dynamic regret, which compares the algorithm against a time-varying optimal sequence. Algorithms must incorporate forgetting mechanisms or sliding windows to track these shifts. Dynamic regret bounds are typically expressed as a function of the total variation in the reward distributions.

In e-commerce, regret minimization algorithms continuously adjust prices to find the optimal balance between margin and conversion rate. The regret is the revenue lost by not showing the ideal price for a specific user context.

• Mechanism: A contextual bandit observes user features (location, device, time) and selects a price point.
• Outcome: The algorithm minimizes the cumulative gap between the chosen price's revenue and the hypothetical optimal price.
• Example: An airline using Thompson Sampling to price seats dynamically, minimizing the regret of selling a seat too cheaply versus not selling it at all.

Traditional randomized controlled trials (RCTs) suffer from high statistical regret because a fixed number of patients receive a suboptimal treatment during the exploration phase. Regret-minimizing bandits offer an ethical and efficient alternative.

• Adaptive Randomization: Algorithms like Thompson Sampling dynamically skew the allocation probability toward the better-performing treatment as data accrues.
• Patient Benefit: This minimizes the regret of assigning patients to inferior arms, ensuring more trial participants receive the effective treatment.
• Regulatory Acceptance: The FDA has issued draft guidance on adaptive trial designs that use these principles to reduce sample sizes and accelerate drug approval.

Static A/B tests incur linear regret while the inferior variant is active. Regret minimization transforms testing into a continuous, self-optimizing process.

• Multi-Armed Bandit Testing: Instead of a fixed 50/50 split, the traffic allocation shifts continuously toward the winning variant.
• Minimizing Opportunity Cost: The regret is the conversions lost by serving the underperforming variant. Algorithms like UCB provide a statistical guarantee that this loss is bounded.
• Production Use: Netflix uses contextual bandits to minimize regret when selecting artwork for its titles, learning user visual preferences in real-time.

For news platforms, user interest decays rapidly. A recommendation engine must minimize the regret of showing a stale or irrelevant article against the optimal choice that would maximize click-through rate.

• Contextual Bandits: The system uses user reading history and current trending topics as a contextual feature vector.
• Exploration-Exploitation: It quickly exploits known breaking news while strategically exploring niche content to discover new interests.
• Yahoo! Today Module: A classic case study where a LinUCB algorithm achieved a 12.5% click lift over a non-contextual baseline by minimizing regret on article selection.

In quantitative finance, regret minimization models the cost of not holding the optimal portfolio. The algorithm sequentially rebalances assets to track the performance of the best single asset in hindsight.

• Universal Portfolios: Cover's algorithm uses regret minimization to guarantee that the portfolio's growth rate asymptotically approaches that of the best retrospectively chosen constant-rebalanced portfolio.
• Transaction Costs: Modern variants incorporate penalty terms for turnover, minimizing a composite regret that balances missed gains against excessive trading fees.
• Adversarial Markets: Unlike mean-variance optimization, regret minimization makes no assumptions about stationary market distributions, making it robust to black swan events.

Mobile keyboards and smart assistants use on-device regret minimization to adapt to user behavior without transmitting sensitive data to the cloud.

• Federated Bandits: The algorithm learns locally on the device, minimizing the regret of poor next-word predictions or app suggestions.
• Privacy Constraint: Because data never leaves the device, the algorithm must efficiently minimize regret with limited computational resources and strict latency budgets.
• Example: Google's Gboard uses federated learning with bandit algorithms to improve query suggestions while minimizing the regret of irrelevant recommendations, all within a TinyML footprint.