# Sequential Batch Learning in Finite-Action Linear Contextual Bandits

arXiv: https://arxiv.org/abs/2004.06321 · HTML: https://mlsanity.com/paper/2004.06321/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

## Built on by (most cited first, 30 of 63)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality](https://mlsanity.com/paper/2202.06450/) (2022)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost](https://mlsanity.com/paper/2205.13170/) (2022)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [HyperBandit: Contextual Bandit with Hypernewtork for Time-Varying User Preferences in Streaming Recommendation](https://mlsanity.com/paper/2308.08497/) (2023)
- [Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits](https://mlsanity.com/paper/2110.08057/) (2021)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Synthetically Controlled Bandits](https://mlsanity.com/paper/2202.07079/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)

## Abstract (arXiv)

We study the sequential batch learning problem in linear contextual bandits with finite action sets, where the decision maker is constrained to split incoming individuals into (at most) a fixed number of batches and can only observe outcomes for the individuals within a batch at the batch's end. Compared with both standard online contextual-bandit learning and offline policy learning in contextual bandits, this sequential batch learning problem provides a finer-grained formulation of many personalized sequential decision making problems in practical applications, including medical treatment in clinical trials, product recommendation in e-commerce and adaptive experiment design in crowdsourcing. We study two settings of the problem: one where the contexts are arbitrarily generated and the other where the context vectors are mutually independent across actions and time and follow a common Gaussian distribution. In each setting, we establish a regret lower bound and provide an algorithm, whose regret upper bound nearly matches the lower bound. As an important insight revealed therefrom, in the former setting, we show that the number of batches required to achieve the fully online performance is polynomial in the time horizon, while for the latter setting, a pure-exploitation algorithm with a judicious batch partition scheme achieves the fully online performance even when the number of batches is less than logarithmic in the time horizon. In the stochastic context setting, we additionally provide tight margin-based (i.e. instance-dependent) upper and lower regret bounds that delineate performance in terms of how difficult the problem instance is. Together, our results provide a near-complete characterization of sequential decision making in linear contextual bandits when batch constraints are present.