Linear Bandits under Exact Sliding-Window Constraints

• Every consecutive window must be feasible, unlike constraints enforced separately each round or only in aggregate, so exploration must respect temporal feasibility.The most recent w −1 actions can be viewed as the state of a finite-memory control problem.Source: §1 · p. 1
• For convex, cyclically invariant constraints, stationary behavior is optimal when w divides T and is within O(w) of the offline optimum otherwise.The offline setting assumes the reward function is known.Source: §1 · p. 1
• In online learning, good stationary actions may be unreachable from one another, making sublinear regret impossible in general.The transition diameter τ quantifies feasible reachability, and rare-switching OFUL preserves exact feasibility with regret ˜O(d√T + τd + w).Source: §1 · p. 2
• For general constraints, recent actions form a finite-memory state, and history-state diameter D measures feasible communication between viable histories.Optimistic remaining-horizon planning with rare policy updates yields regret ˜O(d√T + dD + w).Source: §1 · p. 2
• Recommendation, LLM-routing, and synthetic experiments report exact feasibility, reduced regret in non-cyclic settings, and substantially fewer policy updates.The real-world applications use recommendation diversity constraints and an LLM-routing cost budget.Source: §1 · p. 2

• Long-term constrained methods control cumulative violations, while bandits with knapsacks impose global budgets and safe bandits study pointwise feasibility.Exact sliding-window constraints include pointwise feasibility when w = 1 and can represent horizon-wide constraints when w = T.Source: §2 · p. 2
• Related temporal-learning models allow residual constraint violations, history-dependent rewards, or cumulative constraint violations rather than requiring every window to remain feasible.In the paper's model, exploration must respect exact sliding-window feasibility throughout learning.Source: §2 · p. 2
• Without cyclic symmetry, recent actions form a finite-memory state with deterministic history dynamics and state-dependent feasible actions.Unlike a generic constrained MDP, reward uncertainty is shared across history states through one low-dimensional linear parameter.Source: §2 · pp. 2–3
• Unlike standard limited-switching or switching-cost models, action changes here may require intermediate feasible actions because immediate switching can violate the window constraint.Table 1 compares related sequential-learning frameworks across several key dimensions.Source: §2 · p. 3, Table 1 · p. 3

• The action space is X ⊆ R^d, the horizon is T, the window length is 1 ≤ w ≤ T, and C is the set of feasible action windows.A trajectory is feasible only if every consecutive block of w actions belongs to C.Source: §3 · p. 3
• Every realized block of w consecutive actions must satisfy the constraint exactly.The offline problem assumes the reward function is known.Source: §3 · p. 3
• In the online setting, the learner selects actions sequentially, observes outcomes, and must follow an admissible policy whose trajectory remains feasible.The noise is conditionally mean-zero and R-sub-Gaussian.Source: §3 · p. 3

• The result assumes a nonempty, closed, convex feasible set invariant under cyclic shifts, a compact convex action space, and a concave upper-semicontinuous reward.The cyclic-shift assumption covers a broad class of sliding-window constraints.Source: §4 · pp. 3–4
• For arbitrary horizons, the best stationary solution is within an additive O(w) of the offline optimum.An example establishes that a Θ(w) gap can occur, so the dependence on w is unavoidable.Source: §4 · p. 4
• When w divides T, the stationary action z⋆ maximizes the offline objective over feasible repeated actions and is optimal.The offline value is T f(z⋆).Source: §4 · p. 4

5.1 Why Geometry Alone Is Insufficient

• Offline geometric assumptions alone do not guarantee sublinear online regret when histories induced by good stationary actions are not feasibly connected.A one-dimensional instance shows that sublinear stationary pseudo-regret cannot be guaranteed under Assumption 4.1 alone.Source: §5.1 · p. 4
• The transition diameter τ measures the minimum feasible-update distance between complete histories and must be finite for the proposed reachability guarantee.The section assumes access to an oracle that returns feasible transitions between stationary actions.Source: §5.1 · p. 4

5.2 Feasible Rare-Switching OFUL

• Rare-switching OFUL combines optimistic linear-bandit actions with determinant-doubling episodes and feasible transitions, excluding transition observations from estimation.After an initial action is repeated for at least w−1 rounds, a changed optimistic action is reached through Γ in at most τ rounds.Source: §5.2 · pp. 4–5
• Under the stated online-bandit and reachability assumptions, the algorithm preserves exact feasibility and satisfies the theorem’s regret guarantee.The section also reports that linear dependence on τ is unavoidable, via a one-dimensional instance with Ω(τ) regret.Source: §5.2 · p. 5

6 PLANNING: LEARNING BEYOND CYCLIC SYMMETRY

• Without cyclic symmetry, the optimal feasible trajectory may be inherently non-stationary, motivating a finite-memory control formulation.The most recent w−1 actions form the state, and Bellman recursion describes the offline optimal trajectory.Source: §6 · p. 5, §6.1 · p. 5

6.1 Finite-Memory Representation

• The Bellman value J⋆_n(s) is the optimal reward over feasible n-step continuations from history state s.The n-step viable histories are defined recursively by whether a feasible action leads to an (n−1)-step viable history.Source: §6.1 · p. 5

6.2 History-State Reachability

• The history-state diameter D measures feasible communication across viable histories; for many standard constraints, D = O(w).The definition takes the largest minimum number of feasible updates between histories in S1 and assumes this diameter is finite and independent of T.Source: §6.2 · p. 5

6.3 Rare-Update Optimistic Planning

• The learner combines optimistic linear-bandit estimation with finite-memory Bellman planning, updating its policy only at determinant-doubling times.A new plan is triggered when det(Vt) > 2 det(Vtk).Source: §6.3 · pp. 5–6
• Theorem 6.5 gives a regret guarantee involving history-state diameter D and window length w under the stated online-bandit, finite-diameter, and planning assumptions.Exact Bellman-optimal remaining-horizon planning and feasible initialization are assumed; finite action spaces permit backward dynamic programming, while continuous constraints may need additional structure.Source: §6.3 · p. 6

Recommendation with Diversity Constraints

• On KuaiRand-1K, exact exposure constraints limit how often each category can be recommended within any recent window.The recommendation task seeks user reward while preventing overly repetitive category recommendations.Source: Recommendation with Diversity… · p. 6
• The LLM-routing experiment imposes exact sliding-window cost constraints and uses myopic feasible selection because future query contexts are unavailable at decision time.The routing task selects among models with differing response qualities and inference costs.Source: Recommendation with Diversity… · pp. 6–7

7 EXPERIMENTS

• Across recommendation and LLM routing, Rare-Update Optimistic Planning maintains zero violations while using substantially fewer policy updates than Myopic Feasible OFUL.Recommendation updates are approximately 32, 49, and 57 at T = 500, 2500, and 5000; LLM routing requires 250.2, 789.8, and 1104.8 updates at those horizons.Source: Table 2 · p. 7, Recommendation with Diversity… · pp. 7–8, Table 3 · p. 8
• The evaluation reports average expected reward, normalized pseudo-regret, sliding-window violations, and policy updates against feasible and unconstrained baselines.The baselines include Myopic Feasible OFUL, Primal-Dual OFUL, and Unconstrained OFUL.Source: Recommendation with Diversity… · p. 7

8 CONCLUSION

• For convex cyclically invariant constraints, stationary behavior is optimal when w divides T and within an additive O(w) of the offline optimum otherwise.Online learning additionally depends on feasible reachability, captured by transition diameter τ.Source: §8 · p. 8
• Without cyclic symmetry, recent w−1 actions form a finite-memory state, and history-state diameter D controls communication and continuation-value variation across viable histories.Optimistic remaining-horizon planning yields a regret bound involving dD and w.Source: §8 · p. 8

AI use statement

• The authors report using generative AI to improve manuscript language and review proof drafts, while independently checking proof feedback.They state that AI tools were not used to formulate mathematical claims, develop the framework, design experiments, implement methods, process data, or interpret results.Source: AI use statement · p. 8

A LIMITATIONS AND EXTENSIONS

• The guarantees rely on convexity and cyclic-shift invariance for stationary reduction, and the non-cyclic guarantee assumes finite history-state diameter and exact remaining-horizon planning.For finite action spaces, the history-state space can grow as |X|^(w−1), making exact planning costly for large w.Source: A LIMITATIONS AND EXTENSIONS · p. 11
• Future work includes periodic or recurrent policies for discrete or nonconvex spaces, scalable planning, and determining whether the factor d in the transition term e O(τd) is necessary.Proposition H.7 gives only an Ω(τ) lower bound, so whether the additional factor d can be removed remains open.Source: A LIMITATIONS AND EXTENSIONS · p. 11

B COMPUTATIONAL ORACLES

• Implementation assumes exact optimistic-action and transition oracles, while the general non-cyclic setting also assumes exact remaining-horizon planning.For finite action spaces, backward dynamic programming over viable histories takes O(T|X|^w) time, up to viability preprocessing; continuous constraints require additional structure for efficient planning.Source: B COMPUTATIONAL ORACLES · p. 12

C RELATION TO LINEAR MDPS AND CONSTRAINED REINFORCEMENT LEARNING

• An exact linear-MDP representation of full history-shift dynamics requires p ≥ m^(w−1), exponential in w for fixed m ≥ 2.The paper instead learns a shared d-dimensional reward parameter while handling known history dynamics through planning and history-state diameter D.Source: C RELATION TO LINEAR MDPS AND… · pp. 12–13
• For many constraint classes with D = O(w), the regret bound simplifies to e O(d√T + dw), despite an exponentially large history-state space.The analysis uses known deterministic history dynamics and low-dimensional reward uncertainty rather than depending on the number of history states.Source: C RELATION TO LINEAR MDPS AND… · p. 13
• Exact sliding-window feasibility requires every realized overlapping window to be feasible, while generic safe-RL formulations do not typically exploit the known dynamics and shared d-dimensional reward uncertainty.After augmenting history, feasibility is a state-dependent hard safety constraint; generic linear-MDP or tabular representations may have exponential size in w.Source: C RELATION TO LINEAR MDPS AND… · p. 13

D EXAMPLES OF CONVEX CYCLICALLY INVARIANT CONSTRAINTS

• The appendix illustrates convex cyclically invariant window constraints including aggregate budgets, maximum constraints, ramping, and exponential penalties.The examples include cumulative budgets, worst-case limits, cyclic variation, and penalties that can represent risk, energy consumption, or congestion.Source: D EXAMPLES OF CONVEX CYCLICALLY… · p. 14

E TRANSITION DIAMETER FOR COMMON SLIDING-WINDOW CONSTRAINTS

• Aggregate budget, maximum, box, exponential, ℓp-norm, and convex risk constraints have transition diameter τ ≤ w − 1.The appendix establishes this bound for each listed constraint class, assuming the corresponding stationary feasible set is nonempty.Source: E TRANSITION DIAMETER FOR COMMON… · pp. 15–16
• The construction keeps every generated window feasible and reaches history h(z′) after N+w−2 actions.It plays y1,…,yN and then repeats z′=yN for w−2 rounds.Source: E TRANSITION DIAMETER FOR COMMON… · p. 17
• For aggregate-budget, maximum, box, exponential, ℓp-norm, and convex-risk constraints, distinct feasible stationary actions give transition diameter τ=w−1; cyclic ramping may require more.Source: E TRANSITION DIAMETER FOR COMMON… · p. 17

F HISTORY DIAMETER FOR COMMON CONSTRAINT CLASSES

• State-independent, box, and maximum constraints have history diameter D=w−1 with at least two feasible actions, and D=0 for a singleton action set.Source: F HISTORY DIAMETER FOR COMMON… · pp. 17–18
• For separable additive constraints, resetting to a minimum-cost action and then appending the target history gives D≤2(w−1).The bound applies when the constraint is feasible and the cost function attains its minimum over X.Source: F HISTORY DIAMETER FOR COMMON… · pp. 18–19
• With feasibility and the stated minimum-attainment conditions, aggregate-budget, exponential, aggregate ℓp-norm, and convex-risk constraints each satisfy D≤2(w−1).Source: F HISTORY DIAMETER FOR COMMON… · pp. 19–20
• For compact convex X with w≥2, ρ>0, and positive diameter, the exact non-cyclic ramping history diameter separates movement and memory-replacement costs.Source: F HISTORY DIAMETER FOR COMMON… · pp. 20–21

G.1 Proof of Theorem 4.4

• For a horizon divisible by w, cyclic averaging and concavity produce an optimal stationary feasible trajectory.The proof averages cyclic shifts to obtain a constant feasible window, then uses Jensen’s inequality to compare its reward with the best feasible window.Source: §G.1 · pp. 22–23

G.2 Tightness of the Stationary Approximation Gap

• The O(w) finite-horizon approximation gap is tight: a nonstationary schedule can gain an extra w/4 when the horizon ends partway through a period.Over complete windows, stationary and nonstationary schedules both average 1/2; the gain comes from placing high-reward actions in the final incomplete block.Source: §G.2 · pp. 23–24

H.1 Proof of Proposition 5.2

• When feasibility forces every action to repeat the first, every admissible policy has linear regret for at least one of the two reward signs.The example uses a noiseless one-dimensional reward model with θ⋆ ∈ {−1, 1}.Source: §H.1 · p. 25

H.2 Proof of Theorem 5.4

• Rare-switching OFUL is feasible and achieves expected regret ˜O(d√T + τd + w) against the offline-optimal feasible trajectory.The proof bounds transition rounds through the number of switches and accounts separately for the forced warm-up.Source: §H.2 · pp. 29–30

H.3 A Lower Bound for the Transition Diameter

• For every τ ≥ 2 and T ≥ τ, a one-dimensional instance with transition diameter τ forces Ω(τ) regret, even when the learner learns the true parameter after its first action.This isolates transition cost from learning; the passage also distinguishes statistical d√T and finite-horizon Ω(w) lower-bound scales, and notes that whether the upper bound’s extra factor d is necessary remains open.Source: §H.3 · pp. 31, 33

I.1 Proof of Theorem 6.1

• Representing the last w − 1 actions as a state makes state-dependent feasibility equivalent to the original sliding-window constraints, and Bellman induction yields the optimal feasible continuation value.The proof establishes the equivalence for each round and then uses induction on the remaining horizon to show the recursion attains the optimal value.Source: §I.1 · pp. 33–34

I.2 Proof of Lemma 6.3

• When viable histories can be connected by a feasible transition of at most D steps, the proof compares their continuation values by prepending that bridge and bounding its reward-range cost.The bridge is followed by a feasible n-step continuation; the proof also bounds any extra m actions by m times the reward range.Source: §I.2 · p. 34
• Applying the transition argument in both directions, with a feasible transition from s′ to s of length at most D, completes the claim.The proof combines the two bounds before concluding the claim.Source: §I.2 · pp. 34–35

I.3 Proof of Theorem 6.5

• The theorem proof partitions play into episodes, bounds nonterminal episode regret using optimistic Bellman planning and continuation-value spans, and handles the terminal episode separately.The nonterminal argument follows an optimal continuation for the remaining horizon; the terminal episode follows the optimistic policy to the horizon’s end.Source: §I.3 · p. 35
• The proof telescopes continuation values across episodes, includes initialization terms for w > 1, and bounds the episode count using determinant doubling.It works on a uniform confidence event derived from confidence ellipsoids and states a final probability of at least 1 − δ.Source: §I.3 · pp. 36–37

I.4 Extension to Approximate Remaining-Horizon Planning

• Bounded per-episode planning error degrades regret gracefully; when αmax = O(1), the approximate planner retains the exact planner’s asymptotic rate, and αmax = 0 recovers exact planning.Approximation contributes an explicit cumulative planning-error term.Source: §I.4 · pp. 37, 39

J.1 Offline Geometry and Horizon Misalignment

• For every tested even window length, the maximum stationary approximation gap is w/4 at remainder r = w/2, matching the tightness construction.For w = 32, the gap is zero when the horizon aligns with the window, then rises and falls symmetrically as the remainder changes.Source: Figure 1 · p. 39, §J.1 · p. 40

J.2 Rare Switching under Cyclic Ramping Constraints

• Rare-switching OFUL achieves substantially lower pseudo-regret than Frequent-update feasible OFUL across tested ρ values, with fewer switches and transition rounds and zero violations.Unconstrained OFUL violates the constraint when direct switching is infeasible, but satisfies it at ρ = 2.Source: Figure 2 · p. 40, §J.2 · p. 41

J.3 Planning Beyond Cyclic Symmetry

• Rare-Update Optimistic Planning’s normalized pseudo-regret approaches zero, while Stationary OFUL and Myopic Feasible OFUL retain gaps of approximately 0.1 and 0.15.The stationary gap matches the difference between the best stationary reward, 0.6, and the optimal long-run reward, 0.7; replanning events grow slowly with the horizon.Source: Figure 3 · p. 41, §J.3 · p. 42

K.1 Real-World Ablation Studies

• At T = 5000, optimism achieves lower regret than its non-optimistic variant, while the non-optimistic variant performs better at T = 500 and T = 1000.At T = 2500, the difference is small; the paired difference favors optimism at T = 5000.Source: Figure 4 · p. 42, §K.1 · pp. 42–43
• Across tested routing budgets and horizons, Rare-Update Optimistic Planning maintains competitive reward with zero violations and substantially fewer policy updates.Tighter budgets increase violations for Unconstrained OFUL and Primal-Dual OFUL.Source: §K.1 · p. 42
• In the routing sensitivity experiment, the default threshold α = 2 achieves the lowest pseudo-regret.Source: Figure 5 · p. 43

K.2 Synthetic Ablation Studies

• At α = 2, pseudo-regret is lowest; increasing α from 1.25 to 8 reduces switches from about 135 to roughly 20 and transition rounds from 2700 to 400.Pseudo-regret is non-monotone: very small thresholds incur high transition costs, while very large thresholds adapt more slowly.Source: §K.2 · p. 43
• As action dimension grows with the reward gap fixed at 0.2, exploration costs rise and can produce more target changes and feasibility-preserving transitions.Figure 6 reports pseudo-regret, stationary-target switches, and transition rounds for d ∈ {4, 8, 16, 32}.Source: §K.2 · p. 43, Figure 6 · p. 44
• With T/w fixed at 2048, target switches remain roughly 48–52 as w grows from 2 to 32, while transition rounds rise from about 100 to nearly 4800.Transition rounds per switch increase from 2 to about 92; the stated construction requires 3w−4 rounds per switch, and pseudo-regret also rises as the horizon grows proportionally with w.Source: §K.2 · pp. 43–44, Figure 7 · p. 44
• Normalized pseudo-regret falls from about 0.15 for the myopic policy to below 0.01 under full remaining-horizon planning; updates range from roughly 10 to 16.The number of updates increases only gradually with the planning horizon.Source: §K.2 · pp. 44–45, Figure 8 · p. 45

L IMPLEMENTATION DETAILS

• The implementation details provide publicly available code, preprocessing scripts, and experimental configurations.The paper gives a repository link for these materials.Source: L IMPLEMENTATION DETAILS · p. 45

L.1 Real-World Experiments

• The recommendation experiment uses eight content categories and an exact five-in-twenty exposure constraint; LLM routing uses six models and a sliding-window inference-cost budget.Recommendation actions are category one-hot vectors; LLM features combine query representations with model encodings.Source: §L.1 · pp. 45–46
• To ensure pathwise feasibility without future queries, LLM routing uses a zero-padded prefix convention and a myopic feasible optimistic policy with determinant-based rare updates.The experiment uses H = 1 because future queries are unavailable at decision time.Source: §L.1 · p. 46
• The LLM-routing experiment is not a direct instantiation of Theorem 6.5 because future query-dependent costs are unknown, whereas its regret guarantee assumes known deterministic finite-memory transitions.A zero-cost no-op is used only when no real LLM action is feasible.Source: §L.1 · p. 47

L.2 Synthetic Experiments

• For the synthetic offline experiment, the finite-horizon optimum is computed by linear programming across even window lengths and horizons T = 20w + r.The experiment varies w over even values from 4 to 32 and r from 0 to w−1.Source: Offline geometry and horizon… · p. 49

Offline geometry and horizon misalignment.

• The offline-geometry experiment computes viable histories and exact remaining-horizon plans by dynamic programming, then compares three exactly feasible policies.The comparison separates history-state planning from statistical optimism and stationary-action restrictions.Source: Offline geometry and horizon… · p. 50

L.1 Real-World Experiments

• Across tested budgets, Rare-Update Optimistic Planning maintains competitive reward with zero violations while requiring substantially fewer policy updates.Table 6 reports average reward and normalized pseudo-regret with 95% confidence intervals, and mean violations and updates.Source: Table 6 · p. 51

M ALGORITHMS

• The paper presents two algorithms: Feasible Rare-Switching OFUL for cyclic constraints and Rare-Update Optimistic Planning for general sliding-window constraints.Algorithm 1 uses feasible transitions and determinant-triggered stationary episodes; Algorithm 2 plans from a history state and caches the plan until an update.Source: M ALGORITHMS · p. 52, §M.1 · p. 52, §M.2 · p. 52

M.1 Rare-Switching OFUL

• Feasible Rare-Switching OFUL obtains a feasible transition when its stationary target changes, excludes transition observations from its estimator, and updates targets by determinant doubling.The pseudocode bounds each transition by τ and starts a new episode after the determinant condition is exceeded.Source: §M.1 · p. 52