Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Bayesian Regret Minimization in Offline Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BRMOB, which directly minimizes VaR-based upper bounds on Bayesian regret in offline linear bandits via conic optimization, and argues LCB-style pessimism is inherently suboptimal for regret minimization.
Problem
Minimizing high-confidence Bayesian regret in offline linear bandits, where the common LCB pessimism approach is not known to reduce Bayesian regret.
Approach
Reformulates high-confidence Bayesian regret as a Value-at-Risk of the epistemic uncertainty, upper-bounds the VaR of the max of Gaussian regrets via union-bound (action-set) and credible-region (parameter-space) arguments, and jointly minimizes both bounds with second-order cone programming over randomized policies, with a matching lower bound showing tightness.
Key results
- BRMOB significantly outperforms FlatOPO, Greedy, and Scenario baselines across synthetic domains, especially under large posterior uncertainty; the only challenging regime is k much larger than d.
- Matching lower bound shows the action-set upper bound coefficient is tight up to a constant (ratio below 10 at delta=0.1 for k=1 and non-increasing in k).
- Theory shows LCB with beta above a threshold beta* has higher regret than Greedy, and FlatOPO's beta exceeds beta* for delta=0.1, so LCB is unsuitable for regret minimization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| minimize analytical Bayesian regret upper bounds with BRMOB | BRMOB · Synthetic domains | Bayesian regret | Helped |
| use Greedy instead of FlatOPO | Synthetic domains · Synthetic domains | Bayesian regret | Helped |
| tune FlatOPO's beta coefficient | FlatOPO · Synthetic domains | Bayesian regret | No clear effect |
| use a randomized policy rather than a deterministic policy | BRMOB · Bayesian offline bandits | Bayesian regret | Helped |
Surprising findings
- Greedy (beta=0) outperforms LCB-style FlatOPO in the experiments, and no beta was found for which FlatOPO beats Greedy.
- Penalizing uncertainty via LCB can provably increase Bayesian regret even in simple problems.
Limitations
- Basic version evaluated with m=0 tightening iterations; the tightening improvement is deferred.
- Performance is weaker when k is much larger than d.
- Analysis is for linear bandits with Gaussian or sub-Gaussian posteriors; contextual extension is only suggested.
Experimental setup
Datasets: synthetic Gaussian bandit domains
Benchmarks: synthetic offline linear bandit domains
Metrics: Bayesian regret (high-confidence VaR)
Baselines: FlatOPO Greedy Scenario-based method LCB
Builds on: FlatOPO scenario-based chance-constrained optimization Bernstein technique for linear chance constraints
Closest papers by meaning
- Weighted Bandits or: How Bandits Learn Distorted Values That Are Not Expected (AAAI 2017 · similarity 0.92)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.92)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.92)
- Finite-Time Logarithmic Bayes Regret Upper Bounds (NeurIPS 2023 · similarity 0.91)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.91)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.