aiqbench analysis
This research advances the theoretical understanding of sequential batch learning within linear contextual bandits, offering algorithms that nearly match established lower bounds on regret under specific distributional assumptions. The findings are particularly relevant for practitioners designing adaptive experiments in fields like clinical trials or e-commerce recommendation systems where observing outcomes is constrained to fixed time intervals between batches. By characterizing performance limits and providing efficient partitioning schemes, the work bridges a gap between standard online learning models and practical scenarios requiring delayed feedback aggregation.
Sequential Batch Learning in Finite-Action Linear Contextual Bandits
arXiv:2004.06321v2 Announce Type: replace Abstract: 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.
Abstract: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.
Machine Learning (cs.LG); Information Theory (cs.IT); Machine Learning (stat.ML)
arXiv:2004.06321 [cs.LG]
(or arXiv:2004.06321v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2004.06321 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 363 words
Related coverage
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
arXiv · Aug 19, 2026
Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
arXiv · Sep 10, 2026
Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits
arXiv · Sep 30, 2026
Mixing Makes Markovian Contexts Cheap for Linear Bandits
arXiv · Sep 9, 2026