Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
Not on the map. Why?
Abstract (arXiv)
Linear contextual bandit is an important class of sequential decision making problems with a wide range of applications to recommender systems, online advertising, healthcare, and many other machine learning related tasks. While there is a lot of prior research, tight regret bounds of linear contextual bandit with infinite action sets remain open. In this paper, we address this open problem by considering the linear contextual bandit with (changing) infinite action sets. We prove a regret upper bound on the order of O(√d2Tlog T)× poly(loglog T) where d is the domain dimension and T is the time horizon. Our upper bound matches the previous lower bound of Omega(√d2 Tlog T) in [Li et al., 2019] up to iterated logarithmic terms.
Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 May 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 10; 2023: 0; 2024: 1; 2025: 1; 2026: 3.
17 papers.
Sort:
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
- 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
- 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
- 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
- 2022Variance-Aware Sparse Linear Banditscited by 11
- 2022Stochastic Conservative Contextual Linear Banditscited by 6
- 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
- 2022Provably Efficient Kernelized Q-Learningcited by 4
- 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
5 more
- 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysiscited by 2
- 2022Representation Learning for Context-Dependent Decision-Makingcited by 1
- 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 0
- 2026Learn to Match: Two-Sided Matching with Temporally Extended Feedbackcited by 0
- 2026Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approachcited by 0
- 2026Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach18 Jun 2026
- 2026Learn to Match: Two-Sided Matching with Temporally Extended Feedback4 Jun 2026
- 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions24 Apr 2026
- 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update1 Mar 2025
- 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis21 Jan 2024
- 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms8 Nov 2022
- 2022Lifelong Bandit Optimization: No Prior and No Regret27 Oct 2022
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation23 Jun 2022
- 2022Variance-Aware Sparse Linear Bandits26 May 2022
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs23 May 2022
- 2022Representation Learning for Context-Dependent Decision-Making12 May 2022
- 2022Provably Efficient Kernelized Q-Learning21 Apr 2022
5 more
- 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representation29 Mar 2022
- 2022Stochastic Conservative Contextual Linear Bandits29 Mar 2022
- 2022Non-Stationary Representation Learning in Sequential Linear Bandits13 Jan 2022
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RL8 Feb 2021
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP29 Jan 2021
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
- 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
- 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
- 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
- 2022Variance-Aware Sparse Linear Banditscited by 11
- 2022Stochastic Conservative Contextual Linear Banditscited by 6
- 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
- 2022Provably Efficient Kernelized Q-Learningcited by 4
- 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
12 most cited of 17 All 17 (JSON)
- 2026Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach18 Jun 2026
- 2026Learn to Match: Two-Sided Matching with Temporally Extended Feedback4 Jun 2026
- 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions24 Apr 2026
- 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update1 Mar 2025
- 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis21 Jan 2024
- 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms8 Nov 2022
- 2022Lifelong Bandit Optimization: No Prior and No Regret27 Oct 2022
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation23 Jun 2022
- 2022Variance-Aware Sparse Linear Bandits26 May 2022
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs23 May 2022
- 2022Representation Learning for Context-Dependent Decision-Making12 May 2022
- 2022Provably Efficient Kernelized Q-Learning21 Apr 2022
12 newest of 17 All 17 (JSON)