Linear Bandits under Exact Sliding-Window Constraints

arXiv:2610.08745 · cs.LG · Submitted 2026-10-06 · 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: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Linear Bandits under Exact Sliding-Window Constraints".

Jane: As a diligent AI researcher,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: We’ve talked about how these sliding window constraints make things tricky for linear bandits where you don't know the reward function yet. Now, we’re looking at what this paper actually says about solving that specific problem with exact temporal feasibility.

Jane: Right. Basically, they are taking those hard time restrictions—the sliding windows—and turning them into a finite memory control problem so the AI can actually plan better within those rules.

Tom: Exactly. The main thing they show is that if you know the reward function ahead of time, in the offline setting, and your window size divides your total time horizon, then sticking to one single best action forever is mathematically optimal #pg1.

Lu: That’s a strong result for the offline case because it gives us a clear stopping point. If w divides T, you don't need complex dynamic planning; you just pick the best state and stay there #pg1.

Meng: But what if the time horizon doesn't divide by the window size? Because that happens all the time in real-world deployment, they show that even then, any feasible policy will only lose a small amount of performance compared to a true optimum #pg1.

Jane: That small loss is bounded by something related to w, like O(w). That’s actually pretty reassuring for engineers because it tells you the penalty for not hitting that perfect timing is manageable #pg1.

Tom: Okay, now they move into the online setting, where we don't know the reward function. And here’s where things get more complex than just looking at structure. They argue that just having a nice geometric structure isn't enough on its own to guarantee good long-term regret #pg2.

Jane: They introduce this concept called transition diameter tau. That measures how far you can actually move from one feasible action history to another without violating those time constraints. It’s about the actual reachable space #pg2.

Lu: And that tau is crucial because it’s what they use to build an algorithm, the rare-switching OFUL algorithm, which lets the AI make updates infrequently while still staying on track with feasibility #pg2.

Tom: The expected regret they get there is bounded by O(d sqrt T + tau d + w). That combines the statistical learning part with this geometric reachability tau. It’s a concrete number we can work with #pg2.

Meng: For us at the startup level, that's good because it gives us a way to deploy an AI that doesn't need to constantly update its whole strategy just because of minor temporal shifts. It keeps things stable #pg2.

Jane: And they take it further by handling more general sliding windows, not just the perfectly cyclic ones. They introduce the history-state diameter D for those cases, which measures how well different viable action sequences can communicate with each other #pg2.

Tom: That D is what lets them get a better bound for non-stationary problems. The resulting regret is O(d sqrt T + dD + w) #pg2. It’s about exploiting the communication between histories when things aren't perfectly repeating #pg2.

Lu: They use optimistic remaining-horizon planning and rare policy updates together to achieve that bound, showing that you can find non-stationary optimal behavior without needing a full lookahead at every step #pg2.

Jane: So what this means for the listener is that for any constrained decision AI, you need to measure not just the immediate situation but also how far your viable options are from each other over time. It’s about quantifying that reachability D #pg2.

Tom: Experimentally, they tested these bounds on real recommendation systems and LLM routing tasks. The results showed their approach maintains exact feasibility while requiring fewer policy updates than the old baselines we used in our internal tests #pg2.

Jane: And they specifically compared their method against a stationary version and a myopic version, proving that adding that history-state planning component actually helps isolate the benefit of looking ahead over just sticking to what you know right now #pg2.

Lu: The paper’s big contribution is really the geometry–reachability–planning viewpoint itself. It’s a framework for understanding these temporal constraints by quantifying tau and D #pg1. That’s how we move from just hoping an AI works in a constrained environment to actually bounding its performance based on the problem's shape #pg1.

Meng: From my side, it means we can design systems that are more robust because they understand the constraints geometrically, not just statistically. It moves us away from brittle models that fail when the time horizon shifts slightly #pg2.

Jane: So, if you’re building something sequential where timing matters exactly, this paper tells you how to measure the feasibility of your next move by looking at reachable history and future planning capabilities #pg2.

The paper's summary: Tom: So we’ve seen how they set up these new bounds using that transition diameter tau and history-state diameter D for those general cases. Now, what are the authors suggesting to make this framework even more useful?

Jane: They are pushing for algorithms that use optimistic remaining-horizon planning combined with rare policy updates. It's a way to get the regret bound of O(d sqrt T + dD + w) when you move beyond simple cyclic constraints #pg2.

Lu: That combination is key because it lets the AI exploit non-stationary optimal behavior without needing a full lookahead at every step, which is computationally expensive. They show this works even when things aren't perfectly repeating anymore #pg2.

Meng: From a deployment standpoint, that makes sense because we don't have infinite time to plan ahead for every possibility in real-time. We need something that’s smart about when it decides to look ahead and when it just acts locally based on the current state #pg2.

Tom: They also have some specific bounds for certain constraint classes, like box constraints or aggregate budget constraints, where they can use transition diameter bounds where tau is at most w minus one. That helps keep feasibility preserved during those rare switches #pg1.

Jane: That’s a practical piece of information because it gives us a concrete limit on how much the system can drift without breaking the rules when it does decide to switch its action strategy. It makes those rare policy updates safer #pg1.

Lu: They also look at using an H-step optimistic planner with a truncated lookahead for approximate planning. This helps get a regret bound of O(d sqrt T + dD + w plus d alpha max) #pg2.

Tom: That’s interesting because it means we can benefit from some continuation information even when we have limited computational resources for that planning. It’s about getting the most out of the computation you do spend on looking ahead #pg2.

Meng: If the planning step is truncated, I worry about accuracy at scale. What happens if that approximation introduces errors that cause real-world failures? We need to know how much error we can tolerate before it breaks our production pipeline #pg2.

Jane: That’s the caution there; they are explicitly talking about approximate planning, which means we're trading perfect mathematical certainty for practical speed in a real system, and they acknowledge that trade-off #pg2.

Lu: The overall implication is that this geometry–reachability–planning viewpoint is really the new way to tackle temporal feasibility in constrained learning problems because it gives you measurable metrics like tau and D to guide your model design #pg1.

Tom: So, the takeaway for us as engineers is that instead of just trying different fixed policies, we should be focusing on how well we can measure the feasible reachability and communication between action histories #pg2.

Jane: Exactly. It shifts our focus from just making a good move now to understanding if that move opens up a path to better future moves under the constraints #pg2.

The paper's improvements: Tom: So we’ve gone through how this paper tackles the exact temporal constraints in linear bandits, focusing on those transition diameter tau and history-state diameter D concepts for both cyclic and general sliding windows.

Jane: Right. Basically, they show that by using geometry and reachability metrics instead of just basic structure, we can get much tighter regret bounds for online learning problems #pg2.

Lu: The main implication is that the approach of quantifying feasible communication between different histories, which is what D measures, is a powerful paradigm for tackling these exact temporal feasibility issues in constrained learning problems #pg1.

Meng: For us at the startup level, it means we can design systems that are more robust because they understand the constraints geometrically, not just statistically. It moves us away from brittle models that fail when the time horizon shifts slightly #pg2.

Lalam: I’m confident in this direction because it connects theoretical reachability directly to practical regret bounds #pg1. The paper provides a solid foundation for how AI can handle temporal constraints more intelligently by measuring that feasibility explicitly #pg2.

Tom: It confirms what we suspected: explicit history-state planning gives us better control over the learning process than just relying on basic statistical optimism #pg2.

Jane: And they validate it with real experiments across recommendation systems and LLM routing tasks, showing that the algorithms require substantially fewer policy updates while maintaining exact feasibility #pg2.

Lu: The work provides a framework based on geometry and reachability that we can use to build more robust sequential decision-making AI by quantifying feasible reachability tau and communication D #pg1.

Meng: The cost of calculating that history-state diameter D is still something we need to figure out for production, but the paper gives us the mathematical justification for why it’s worth investing in those complex representations #pg2.

Lalam: I’m sure this framework will be a lot of reference material as we try to deploy these complex sequential decision-making models in real-world scenarios #pg1.

Conclusion: Tom: So we've looked at how "Linear Bandits under Exact Sliding-Window Constraints" tackles those tricky time restrictions using geometry and reachability metrics for both online and offline learning problems.

Jane: Right, they show that by measuring feasible reachability and communication between different action histories, we can get tighter regret bounds for online learning problems.

Lu: The main implication is that quantifying that communication, which they call the history-state diameter D, is a powerful paradigm for tackling these exact temporal feasibility issues in constrained learning problems.

Lalam: I’m confident in this direction because it connects theoretical reachability directly to practical regret bounds. The paper provides a solid foundation for how AI can handle temporal constraints more intelligently by measuring that feasibility explicitly.

Tom: It confirms what we suspected: explicit history-state planning gives us better control over the learning process than just relying on basic statistical optimism.

Tom: So, to wrap up, this paper on "Linear Bandits under Exact Sliding-Window Constraints" shows that even with strict time windows, we can get rigorous regret bounds by focusing on how far we can actually move between viable action histories.

Jane: That’s the core message: measuring feasible reachability and communication is the way forward for handling these exact temporal constraints in learning problems.

Lu: It sets a clear direction for future work on representation learning, showing that incorporating geometric properties directly into the planning step yields measurable performance gains.

Meng: I think if we can make calculating D faster, this framework could be used to build much more stable AI systems for time-sensitive applications in the near term.

Lalam: I’m sure this framework will be a lot of reference material as we try to deploy these complex sequential decision-making models in real-world scenarios.

Tom: Next up, we've got a paper on how LLMs suppress cultural knowledge through alignment training. We'll see if that suppression is something we can actually fix.

Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar Vakili

University of California, Los Angeles

cs.LG

Submitted: 2026-10-06

Updated: 2026-10-06

Comments: 53 pages, including supplementary material; 8 figures and 6 tables

Code: https://github.com/ynulihao/LLMRouterBench

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: As a diligent AI researcher, I have meticulously analyzed both provided texts from the arXiv paper "Linear Bandits under Exact Sliding-Window Constraints." The first text provides a high-level

Key concepts

Transition Diameter ($ au$): This concept measures the maximum feasible distance between two states within the constraints of the sliding window. It quantifies how far one action sequence can feasibly reach another, which is crucial for designing algorithms that ensure every step taken remains valid under temporal rules.
History-State Diameter ($D$): This metric measures the feasible communication or connectivity between different viable sequences of past actions (histories). It quantifies how well one history can transition to another while respecting the sliding window and feasibility rules, allowing for better planning in complex scenarios.
Exact Sliding-Window Constraints: These are temporal restrictions requiring that every consecutive block of actions must belong to a predefined set of feasible sequences. This constraint forces the learning process to respect strict sequential dependencies rather than just optimizing rewards independently.
OFUL Algorithm: This is a rare-switching Offline-Optimal Unconstrained Linear algorithm. It is an approach used in the online setting that combines optimistic planning with infrequent policy updates, designed to achieve good regret bounds even when geometric structure alone isn't enough for learning.

Summary

As a diligent AI researcher, I have meticulously analyzed both provided texts from the arXiv paper Linear Bandits under Exact Sliding-Window Constraints. The first text provides a high-level overview of the theoretical contributions and key results, while the second text details specific experimental setups and algorithmic comparisons.

Here is a comprehensive, detailed summary combining these elements:

Detailed Research Summary: Linear Bandits Under Exact Sliding-Window Constraints

This research investigates the optimal learning strategies for linear bandits operating under strict temporal constraints where every consecutive block of actions must adhere to a prescribed feasible set (a sliding window). The study addresses both offline (reward function known) and online (reward function unknown) settings, focusing on how structural properties like convexity and cyclic symmetry influence performance.

Theoretical Framework and Key Findings

The paper establishes a framework that bridges control theory, finite-memory systems, and bandit optimization by treating the recent action history as a state in a finite-memory control problem. This approach is crucial for handling the exact temporal feasibility constraints.

1. Offline Setting Analysis (Convex & Cyclic Constraints):

For the specific case where constraints are convex and cyclically invariant, the authors prove that a stationary policy is optimal when the window size w divides the total time horizon T (w T). In cases where this condition does not hold, they demonstrate that any feasible policy will yield an offline regret within an additive gap of O(w) compared to the true offline optimum.

Key Result (Theorem 4.4): The stationary trajectory x t = z is optimal if w T, and the value function difference is bounded by r over f - f(z) at most (w-1)f - f(z), where T = qw + r.

2. Online Setting Analysis (Geometric Structure Insufficiency):

The study rigorously demonstrates that relying solely on the geometric structure of the constraints is insufficient for achieving sublinear regret in the online setting. The authors introduce a critical concept, **transition diameter tau **, which quantifies feasible reachability between states.

Key Result (Theorem 5.4): Under specific assumptions, a rare-switching Offline-Optimal Unconstrained Linear (OFUL) algorithm is shown to be feasible and achieves an expected pseudo-regret of O(d sqrt T + tau d + w). This bound is derived by combining the offline gap analysis with the online regret bound.
Lower Bound Insight: A proposition (H.7) establishes a lower bound on tau, showing that for certain instances, every admissible policy must incur a regret of at least tau/4, where tau relates to the transition diameter.

3. General Sliding-Window Constraints (History-State Formulation):

The authors extend the analysis beyond cyclic constraints to general sliding-window constraints, where optimal behavior may be non-stationary. They reformulate this as a finite-memory control problem by representing recent action history as the state, and introduce the **history-state diameter D **, which measures feasible communication between viable histories.

Key Result (Theorem 6.5): By combining optimistic remaining-horizon planning with rare policy updates, they obtain a regret bound of O(d sqrt T + dD + w). This result is obtained by considering the general case and showing that the optimal behavior can be approximated by policies that utilize this history-state diameter.

Algorithmic Development

The theoretical results are supported by two primary algorithms designed to navigate these constraints:

Feasible Rare-Switching OFUL (Algorithm 1): Designed for the cyclic setting, this algorithm leverages the transition diameter tau to ensure feasibility while employing rare updates based on optimistic planning.
Rare-Update Optimistic Planning (Algorithm 2): This extension is tailored for general sliding-window constraints, utilizing the history-state diameter D to guide policy updates via a rare-update principle.

Experimental Validation

The theoretical bounds are validated through extensive experiments across diverse real-world scenarios, including:

Real-world recommendation systems.
Large Language Model (LLM) routing tasks.
Synthetic benchmark tasks.

The experimental results confirm the paper's claims: the proposed approach maintains exact feasibility while achieving reward and regret performance comparable to existing baselines, but crucially, it requires substantially fewer policy updates. The comparison between three policies—Feasible Rare-Switching OFUL, Myopic Feasible OFUL (which lacks continuation value planning), and Stationary OFUL—is used to isolate the contribution of explicit history-state planning versus statistical optimism and stationary restriction.

Conclusion

The paper concludes that the geometry–reachability–planning viewpoint is a powerful paradigm for tackling the complexity introduced by exact temporal feasibility in constrained learning problems. By quantifying feasible reachability (tau) and communication between histories (D), the authors provide robust regret bounds that account for both temporal constraints and history-dependent dependencies, offering a significant advancement over methods relying only on basic geometric structures.

Improvements for AI systems

Use a rare-switching OFUL algorithm to learn in online linear bandits under exact sliding-window constraints by achieving expected pseudo-regret Oe(d√T + τ d + w) against the offline optimal feasible trajectory. This allows the AI system to maintain exact feasibility while reducing policy updates compared to baselines.
Implement a history-state diameter D derived from the problem's geometry, leading to a regret bound of Oe(d√T + dD + w) for general sliding-window constraints, enabling learning where geometric structure alone is insufficient for learning.
Utilize optimistic remaining-horizon planning combined with rare policy updates to obtain a regret bound of Oe(d√T + dD + w) when moving beyond cyclic invariance, allowing the AI to exploit non-stationary optimal behavior.
For specific constraint classes (e.g., box constraints, aggregate budget constraints), leverage the derived transition diameter bounds τ ≤ w − 1 to ensure feasibility preservation during rare switches.
Employ an H-step optimistic planner with a truncated lookahead to achieve a regret bound of Oe(d√T + dD + w + dαmax) when using approximate planning, allowing the AI to benefit from continuation information even with limited computational resources.

Abstract

We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when w T and within an additive O(w) gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter τ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret (d sqrt T +τd+w) against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter D that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of (d sqrt T +dD+w). We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.