Research map / Bandits and online learning / Multi-armed bandits
Finite-Time Logarithmic Bayes Regret Upper Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use finite-time, gap-dependent BayesUCB analysis instead of prior \tilde{O}(\sqrt{n}) analysis | BayesUCB on K-armed Gaussian bandits · K-armed Gaussian bandit | Bayes regret upper bound: O(c_Δ log n) vs. \tilde{O}(\sqrt{n}) | Helped |
| Use the prior-dependent complexity bound that integrates out random gaps | BayesUCB on K-armed Gaussian bandits · K-armed Gaussian bandit | Bayes regret upper bound: O(c_h log^2 n) | Helped |
| Use a more informative prior | BayesUCB · Gaussian bandits | Bayes regret | Helped |
| Use prior information rather than an algorithm oblivious to the prior | BayesUCB versus UCB1 · Gaussian bandits | Bayes regret | Helped |
| Apply the finite-time Bayesian confidence-bound analysis to a linear bandit | BayesUCB · Linear bandit with Gaussian rewards | Bayes regret upper bound: O(d c_Δ log^2 n) vs. \tilde{O}(\sqrt{n}) | Helped |
| Increase the prior gap | BayesUCB · Linear bandit with Gaussian rewards | Bayes regret | Helped |
| Make the prior increasingly informative | UCB1 · Gaussian bandits | Bayes regret | No clear effect |
| Use a gap-dependent logarithmic bound when the random gaps are small or the prior complexity term is large | BayesUCB · Bayesian bandits | Bayes regret upper bound: O(c_Δ log n) or O(c_h log^2 n) vs. \tilde{O}(\sqrt{n}) | Hurt |
Closest papers by meaning
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.91)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.91)
- Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits (ICML 2021 · similarity 0.90)
- Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms (NeurIPS 2024 · similarity 0.90)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.89)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.89)
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.