Sequential Batch Learning in Finite-Action Linear Contextual Bandits

arXiv:2004.06321 · cs.LG, cs.IT, math.IT, stat.ML · Submitted 2026-08-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Sequential Batch Learning in Finite-Action Linear Contextual Bandits".

Jane: The paper was written by Yanjun Han, Zhengqing Zhou, Zihao Hu, Jose Blanchet, Peter W. Glynn et al. from Stanford University and New York University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everybody. Today we’re digging into a paper that just hit arXiv, and it’s called “Sequential Batch Learning in Finite-Action Linear Contextual Bandits.” Jane, I have to say, the title alone sounds like a mouthful, but the idea behind it is actually something we all deal with in daily life.

Jane: Absolutely, Tom. And I think the best way to explain it is to think about how a doctor runs a clinical trial. You don’t test a drug on one patient at a time and immediately change your approach for the next patient. You treat a whole group, wait for the results, then adjust for the next group. That’s a batch. And this paper asks: how well can you learn when you’re forced to operate in batches instead of getting feedback instantly?

Tom: Right, and that’s the “sequential batch learning” part. The “linear contextual bandits” part is the mathematical framework. Basically, you have people coming in one by one, each with their own features—like age, medical history, whatever—and you have a set of actions you can take, like which drug to prescribe. The reward you get depends on both the person’s features and the action you pick.

Jane: And the key constraint here is that you can’t see the reward until the whole batch is done. So you’re making decisions for a whole group of people, then you wait, then you learn, then you make decisions for the next group. The authors—Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter Glynn, and Yinyu Ye—they’re asking a really fundamental question: how much does this batching slow you down?

Tom: And the answer, Jane, is that it depends on how the contexts—those individual features—are generated. If an adversary can choose the features to mess with you, you need a lot more batches to catch up. But if the features are drawn randomly from a nice distribution, you can get away with surprisingly few batches.

Jane: That’s the big insight. And the math they use to prove it is pretty heavy—lots of regret bounds, confidence intervals, and concentration inequalities. But the intuition is clean. It’s like studying for an exam. If the questions are random, you can guess the material pretty well after a couple of practice tests. But if someone is deliberately writing questions to trip you up, you need many more practice rounds.

Tom: So the paper is essentially giving us a roadmap for how to design these batch experiments in the real world. Whether it’s clinical trials, marketing campaigns, or even crowdsourcing, knowing how many batches you need to get good performance is incredibly valuable.

Jane: And that’s exactly what we’re going to dig into next. We’ll look at the two settings they studied—adversarial contexts versus stochastic contexts—and why the difference matters so much.

Tom: Stay with us, folks. We’re just getting warmed up.

Summary: Tom: So we’ve set the stage. Now let’s get into the meat of “Sequential Batch Learning in Finite-Action Linear Contextual Bandits.” Jane, what did the authors actually prove?

Jane: Well, Tom, they split the problem into two worlds. First, the adversarial world, where the contexts—those individual features—are chosen by an adversary who knows what you’ve done in the past. In that world, they show that if you have M batches, your regret—the amount of reward you miss out on compared to a perfect oracle—is roughly on the order of the square root of dT plus dT over M. Here d is the dimension of the features and T is the total number of people.

Tom: And that means, if you want to match the fully online performance—where you get feedback after every single person—you need about the square root of dT batches. That’s a lot. For a constant dimension, that’s about the square root of T batches. So if you have a thousand people, you need about thirty batches to do as well as if you could learn instantly.

Jane: Exactly. And they also proved a lower bound saying you can’t do much better. So that’s tight, up to some logarithmic factors. But then they looked at the second world, the stochastic world, where the contexts are drawn independently from a fixed distribution, like a bell curve. And here’s the shocker: you only need about log-log of T batches to achieve the same performance.

Tom: Log-log of T. That’s doubly logarithmic. For a thousand people, that’s like three or four batches. For a million people, it’s still only about four or five batches. That’s a massive difference from the adversarial case.

Jane: Right. And the algorithm they propose in the stochastic world is almost embarrassingly simple. It’s pure exploitation. You estimate the underlying parameter using the data you have, and then you just pick the action that looks best according to that estimate. No fancy exploration. No upper confidence bounds. Just greedily go with your best guess.

Tom: And that works? Even though you’re not deliberately exploring?

Jane: That’s the beautiful part. Because the contexts are random, the data you collect naturally covers all directions in the feature space. So your estimate gets better and better, and the regret shrinks at a rate that’s essentially optimal. They prove it with a lemma that shows the matrix of selected contexts is well-conditioned, meaning you’re not missing any important direction.

Tom: So the randomness of the contexts does the exploration for you. That’s a really elegant result. And it has a direct practical implication: if you’re running a clinical trial and the patients are coming in with random characteristics, you don’t need to deliberately randomize your treatment assignments. You can just treat everyone with your current best guess, and you’ll still learn fast enough.

Jane: But there’s a catch, and that’s what we’re going to talk about next. The regret bounds we just mentioned are what they call “gap-independent.” They don’t care about how different the actions are. But in the real world, sometimes one action is clearly better than another, and that gap can make learning much easier.

Tom: So there’s a problem-dependent version of this. Let’s dig into that in the next segment.

Improvements: Tom: Welcome back. So we’ve seen the worst-case bounds, but now we’re getting into the part of “Sequential Batch Learning in Finite-Action Linear Contextual Bandits” that feels more practical. Jane, what happens when the actions are not all equally good?

Jane: Great question. In the stochastic world, they also studied a setting where one action is clearly better than the other. They call this the problem-dependent case. And here, the regret can be much smaller. Instead of scaling with the square root of T, it scales with T to the power of one over M. So if you have more batches, the regret drops much faster.

Tom: So for a fixed number of batches, the regret is like T to the one/M. That means with two batches, you’re looking at T to the one-half, which is the same as the square root. But with three batches, it’s T to the one-third, which is much better. And with four batches, it’s T to the one-fourth.

Jane: Exactly. And they prove both an upper bound and a lower bound that match, up to logarithmic factors. So they’ve nailed down the exact rate. The key quantity here is the norm of the true parameter, theta star. If that norm is large, meaning the actions are very different in terms of their expected rewards, then learning is easier and the regret is smaller.

Tom: So the bigger the gap between the best and second-best action, the faster you learn. That makes intuitive sense. If one drug is clearly better for everyone, you’ll figure that out quickly. But if they’re almost identical, you need a lot more data to tell them apart.

Jane: Right. And the algorithm they use is the same pure-exploitation algorithm, but with a different grid. Instead of the geometric grid they used for the worst-case bound, they use a grid where the batch sizes grow geometrically with a different base. The base is chosen based on the horizon and the dimension, and it ensures that the regret is balanced across batches.

Tom: So the improvement here is not just in the analysis, but also in the algorithm design. They’re showing that the choice of batch sizes matters a lot, and they give a concrete recipe for how to choose them.

Jane: And that’s a big deal for practitioners. If you’re running an experiment and you have a fixed number of batches, you can now compute the optimal batch sizes ahead of time. You don’t need to adaptively decide as you go. You just plug in the horizon, the dimension, and the number of batches, and you get your grid.

Tom: So this is a very actionable result. But I have to ask, what about the case where the number of batches is really small, like two or three? Does the algorithm still work well?

Jane: It does. For example, with three batches, the regret is on the order of T to the four/seven which is about T to the zero point five seven. That’s better than the square root of T, which is T to the zero point five, but not by a huge amount. With more batches, the exponent gets closer to zero, meaning the regret grows very slowly.

Tom: So the gains from adding batches are diminishing, but they’re real. And the paper gives you the exact trade-off. Now, let’s bring in our senior researcher, Lu, to get a bigger picture on what this means for the field.

Lu: Thanks, Tom. I think the most exciting implication here is that this paper bridges a gap between offline and online learning. In many real-world applications, you can’t do fully online learning because of logistical constraints, but you also don’t want to just do a single offline batch. This paper gives you a middle ground with provable guarantees. And the fact that you can achieve near-optimal performance with just a handful of batches in the stochastic case is a huge practical win.

Tom: And with that, let’s wrap up our discussion and move to the conclusion.

Conclusion: Tom: Alright, we’ve covered a lot of ground on “Sequential Batch Learning in Finite-Action Linear Contextual Bandits.” Let’s bring it all together. Jane, what’s the one-sentence takeaway for our listeners?

Jane: The takeaway is that the number of batches you need to learn effectively depends critically on whether the contexts are adversarial or stochastic. In the adversarial case, you need roughly the square root of T batches to match fully online performance. In the stochastic case, you only need about log-log of T batches, which is almost nothing.

Tom: And the algorithms are surprisingly simple in the stochastic case. Pure exploitation, no deliberate exploration, just greedily pick the best action according to your current estimate. That’s a beautiful result because it’s so easy to implement.

Jane: And they also gave problem-dependent bounds that show you can do even better when there’s a clear gap between actions. The regret scales like T to the one/M, so more batches help a lot in that regime.

Lu: I’d add that the lower bounds they proved are just as important as the upper bounds. They show that their algorithms are essentially optimal, up to logarithmic factors. That gives practitioners confidence that they’re not leaving performance on the table.

Meng: And from an engineering standpoint, the grid selection is a concrete, plug-and-play formula. You know your horizon, your dimension, and your batch count, and you can compute the batch sizes ahead of time. That’s something we can actually implement in a production system.

Tom: So whether you’re running clinical trials, A/B tests, or recommendation systems, this paper gives you a clear framework for how to design your experiment when you can’t get feedback instantly. It’s a significant contribution to the contextual bandits literature.

Jane: And with that, we’re going to say goodbye to this paper. Thanks to everyone who tuned in. We’ll be back with the next arXiv paper soon. Until then, keep learning, and remember—sometimes a few well-chosen batches are all you need.

Yanjun Han, Zhengqing Zhou, Zihao Hu, Jose Blanchet, Peter W. Glynn, Yinyu Ye, Zhengyuan Zhou

Stanford University · New York University

cs.LG, cs.IT, math.IT, stat.ML

Submitted: 2026-08-16

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 67/100

Key concepts

Contextual Bandits
This mathematical framework involves individuals with specific features, such as age or medical history. The system chooses an action, like a drug, and the resulting reward depends on both that specific person's features and the action selected.
Sequential Batch Learning
This describes a learning process where decisions are made for groups (batches) of people. Instead of receiving feedback after each individual interaction, you wait until the entire batch is complete to see results before adjusting your strategy for the next group.
Adversarial Context
In this setting, an opponent deliberately chooses the features of individuals to confuse the learning system. This worst-case scenario requires a large number of batches—roughly the square root of total people—to achieve optimal performance.
Stochastic Context
This is a favorable environment where individual features are drawn randomly from a fixed distribution, like a bell curve. The randomness allows the algorithm to learn very quickly, requiring only about log-log of total people in batches.

Terminology

Summary

Summary

This paper studies the problem of sequential batch learning in linear contextual bandits with a finite number of actions. In this setting, 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. This is contrasted with standard online contextual bandits (where feedback is immediate) and offline policy learning (where no active learning is possible). The paper notes that this batch constraint is common in practice, citing examples such as medical treatment in clinical trials, product recommendation in e-commerce, and adaptive experiment design in crowdsourcing.

The paper studies two settings: one where contexts are arbitrarily generated (adversarial contexts) and one where contexts are drawn iid from a Gaussian distribution (stochastic contexts). The main contributions are regret upper and lower bounds for both settings.

1. Adversarial Contexts Setting

In the adversarial contexts setting, the contexts x t,a can be arbitrarily chosen by an adversary, with k x t,a k 2 1. The paper provides a UCB-style algorithm adapted to the sequential batch setting (Algorithm 1, SBUCB) which uses a uniform grid t m = mT/M. The main result (Theorem 1) is:

  • Upper bound: There exists a sequential batch learning algorithm such that:

[

theta: theta 2 1 E theta[R T(Alg)] polylog(T) times (sqrt dT + dT over M)

]

under Assumption 1 (K = O(poly(d)) and T d squared).

  • Lower bound: For K=2 and any sequential batch learning algorithm:

[

theta: theta 2 1 E theta[R T(Alg)] c times (sqrt dT + T sqrt d over M, T over sqrt M)

]

where c > 0 is a universal constant.

The paper concludes that in the adversarial contexts setting, (sqrt dT) batches are sufficient to achieve the fully online regret (sqrt dT). The upper bound is achieved by a master algorithm (SupSBUCB) that resolves a conditional independence issue in the vanilla UCB algorithm, at the cost of a multiplicative O(T) factor in regret.

2. Stochastic Contexts Setting

In the stochastic contexts setting, contexts are iid drawn from a Gaussian distribution N(0,) with kappa/d lambda lambda 1/d (Assumption 2). The paper reveals a sharp contrast with the adversarial case: a simple pure-exploitation algorithm (Algorithm 4) achieves near-optimal performance with far fewer batches. The main result (Theorem 2) is:

The paper concludes that in the stochastic contexts setting, it is necessary and sufficient to have ((T/d 2)) batches to achieve the fully online regret (sqrt dT). The upper bound is achieved by a sample-splitting master algorithm (Algorithm 5) that ensures conditional independence of rewards given contexts, at the cost of a multiplicative factor of M = O(T) in sample size.

3. Problem-Dependent Regret Bounds

The paper also provides problem-dependent (gap-dependent) regret bounds for the stochastic contexts setting with K=2. Theorem 3 states:

The paper concludes that in this setting, it is necessary and sufficient to have ((T/d 2)) batches to achieve the optimal problem-dependent regret (d 3/2/ theta 2).

Key Technical Lemmas

The proofs rely on several key lemmas:

  • Lemma 1: A concentration result showing that the estimated parameter m-1 is close to the true theta with high probability, under a conditional independence assumption.

  • Lemma 3: A bound on the sum of traces of inverse covariance matrices: sum m=1 M sqrt Tr(A m-1-1 X m) sqrt 10 (T+1) times sqrt Md + d T over M.

  • Lemma 4: A result showing that the matrix formed by selected contexts in a batch is well-conditioned: lambda (sum t=t m-1+1 t m x t,a t x t,a t) c times kappa (t m - t m-1)/d with high probability.

  • Lemma 5: A bound on the estimation error: m - theta 2 C d sqrt T / (kappa t m) with high probability, under a conditional independence assumption.

  • Lemma 7: A minimax lower bound for any fixed grid: theta E[R T(pi)] times sum m=1 M t m - t m-1 over sqrt d (-16 t m-1 squared over d squared).

  • Lemma 8: Properties of the tilted distributions Q 1, Q 2 used in the lower bound proof, including the identity Z 0 r t / (10 sqrt d) and E Q 1[(u t theta) 2] = 2 2/(d+1).

Conclusion

The paper provides a near-complete characterization of sequential decision making in linear contextual bandits with batch constraints. The key insight is that the nature of the contexts (adversarial vs. stochastic) has a profound impact on the optimal achievable performance and the algorithms required to achieve it. In the adversarial case, (sqrt dT) batches are needed for optimal performance, while in the stochastic case, only ((T/d 2)) batches are needed.

Improvements for AI systems

Based on the scientific paper, here are specific improvements I can make to AI systems and what the improved systems can do:

Improvement: Implement a sequential batch learning layer that partitions incoming data into a fixed number of batches (M) and delays reward incorporation until batch completion, rather than assuming immediate per-sample feedback.

What the improved AI system can do:

  • Operate effectively in environments where feedback is only available at batch boundaries (e.g., clinical trials with 3-5 phases, marketing campaigns with weekly reporting cycles)

  • Automatically determine optimal batch sizes using the grid selection formula: t1 = Θ(√(T·d2)(1/(2(2M-1)))), tm = ⌊a·tm−1⌋

  • Achieve near-optimal regret (within polylog factors) even when feedback is delayed by an entire batch

Improvement: Add a context-type detector that switches between two algorithms:

  • Adversarial contexts: Use Sequential Batch UCB (Algorithm 1) with confidence bounds γ√(xTA−1x) and uniform grid tm = ⌊mT/M⌋

  • Stochastic contexts: Use Sequential Batch Pure-Exploitation (Algorithm 4) with geometric grid and least-squares estimation

Improvement: Implement the master-base algorithm structure (Algorithms 2-3 and 5) that partitions each batch into disjoint time frames for estimation, ensuring conditional independence of rewards given contexts.

Improvement: Add a margin-detection mechanism that estimates kθ*‖2 and switches to the gap-dependent algorithm when the margin is large.

Improvement: Use batch-specific confidence bounds that account for the reduced information available at each batch boundary, with γ = 1 + √(½·log(2KT2)) and Lemma 5's bound ‖θ̂m - θ*‖2 ≤ C·√(d·log(T)/(κ·tm)).

Improvement: Integrate the theoretical lower bounds from Theorems 1-3 to predict achievable performance before deployment.

Improvement: Extend the stochastic context algorithm to handle sub-Gaussian or bounded contexts by replacing the Gaussian-specific Lemma 4 with concentration inequalities for general distributions (using Lemma 10 for Wishart matrices).

The improved AI system can:

  • Deploy in batch-constrained environments (clinical trials, marketing, crowdsourcing) with provable performance guarantees

  • Automatically adapt to context type (adversarial vs. stochastic) and problem difficulty (margin size)

  • Achieve near-optimal regret with minimal batches (e.g., 3 batches for stochastic contexts achieve Õ(d(5/14)T(4/7)) regret)

  • Provide reliable uncertainty estimates even with delayed feedback

  • Predict performance limits before deployment, enabling better resource allocation

  • Maintain statistical validity through sample-splitting and master-base architectures

Sources

Related papers