acceptodds
Under review as a conference paper at ICLR 2027

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

11 views

Abstract

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner’s trajectory. We prove a high-probability regret bound of , where is the learning horizon, is the parameter dimension, is the memory length, and bound the memory-map operator norm and reward-parameter norm, respectively, and is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory–horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Primary area:
learning theory
Keywords:
linear bandits, non-stationary bandits, regret

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_RHC6OpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies linear bandits with finite action-dependent memory, where recent actions determine a known memory state that affects current rewards. The authors propose RSM-LinUCB, which combines linear-bandit confidence sets with Bellman planning over memory states and determinant-triggered rare policy updates. The method achieves a regret bound of O~(dRS(M+1)+σdT)\widetilde{O}(dRS(M+1)+\sigma d\sqrt{T}), replacing the multiplicative memory–horizon dependence in prior work with an additive memory cost, and the paper provides a matching lower bound up to logarithmic factors. The framework is further extended to generalized linear rewards, and experiments on synthetic and semi-synthetic caching tasks support the theoretical findings.

Critical strengths
  1. Strong conceptual and theoretical contribution. The Bellman-centric view of linear bandits with memory is well motivated: the recent action history forms a known deterministic state, while only the reward parameter needs to be learned. Combining optimistic linear-bandit estimation, Bellman planning, and rare policy updates leads to a substantially sharper regret bound with additive memory dependence. The matching lower bound further shows that this improvement is essentially minimax-optimal, which is a major reason for my positive overall assessment.

  2. Relatively complete treatment of the problem. Beyond the basic linear setting, the paper extends the framework to generalized linear rewards and provides corresponding theoretical guarantees. The synthetic and semi-synthetic KV- and semantic-cache experiments also provide useful empirical support for the proposed approach, making the overall contribution both theoretically deep and reasonably well validated.

Critical weaknesses
  1. Computational tractability of the Bellman planning step remains a limitation. In the general formulation, the memory state space is AM\mathcal{A}^M, which can be very large or even continuous, and the paper does not provide a generally efficient implementation of the planning step. For a primarily theoretical paper, I do not view this as a fatal issue. Still, it would strengthen the paper if the authors could discuss more concrete approximation strategies or structural conditions under which Bellman planning can be carried out efficiently while approximately preserving the theoretical guarantees.

  2. The assumption that the memory map A(s)A(s) is known may limit applicability. This assumption is reasonable in system-controlled settings such as caching, but may be less realistic for applications such as recommendation fatigue or behavioral carry-over effects, where the memory dynamics are not directly known. The paper would benefit from a clearer discussion of how such a memory map could be specified, estimated, or obtained in realistic applications, and what happens when the assumed map is only approximate.

Questions for authors

See weakness.

4 comments

We sincerely thank the reviewer for recognizing the motivation, conceptual and theoretical contributions, general framework, and empirical validation of our work.

We agree with the reviewer that two important aspects deserve further clarification: the computational tractability of the planning step and the assumption of a known memory map. We have revised the manuscript to address these concerns through expanded discussions of approximation methods and tractable planning structures in Remark 2 and Appendix C, and additional discussions of the known memory map and its possible extension to unknown memory maps in Sections 2 and 7. We believe these revisions have substantially improved the clarity and practical scope of the manuscript.

We provide the detailed responses to each question below.

1. Computational tractability and approximation (W1).

Question: The planning step may be computationally expensive for large memory state spaces. What concrete approximation strategies can be used, and under what additional structure can planning be made efficient while retaining theoretical guarantees?

Response: We agree that the planning step can be computationally expensive and it motivated our Remark 2 in the initial submission to discuss the approximation approaches and the role of application-specific structure. For general memory maps, exact planning can be computationally hard even under the full information. We therefore distinguish between generic numerical approximations and structured cases where stronger guarantees are available.

We provide two general approximation approaches for the planning. For small state spaces, discounted Howard policy iteration computes JkJ_k near-exactly. We show in Theorem 5 in Appendix C.1 that an O(Tlog⁡T)O(T\log T) iteration budget preserves the regret order. For larger problems, projected gradient ascent provides a practical approximation. This approach was also used in [1, 2] and discussed in our initial submission (see Appendix C.4 in the revised manuscript). A general regret guarantee for this approximation remains open.

⇒\Rightarrow In the revised manuscript, we have clarified these approximation techniques in Remark 2 (p. 5, lines 246–258).

We also characterize structural conditions when tractable exact planning is achievable. One sufficient condition is when histories admit polynomially many effective states that determine both the reward feature and the next effective state after any action. For example, the hard-gate memory map in synthetic experiments in Section 6 tracks only the last action and its consecutive run length, giving O(nM)O(nM) states with n=∣A∣n=|\mathcal A| denoting the size of action set, and modeling setup delays after switching operating modes. A direct implementation retains Theorem 1's regret bound and takes polynomial time of O~(d3+nd2+n2M)\widetilde O(d^3+nd^2+n^2M) per replanning call.

⇒\Rightarrow In the revised manuscript, we have clarified the condition and highlighted this example in Remark 2 (p. 5, lines 259–264); the exact implementation is described in Appendix C.3 (p. 19–20, lines 998–1029).

We further exploit the structural properties in KV-cache and semantic cache applications in our numerical experiments, and develop dedicated polynomial-time replanning approximation with an additional O~(d)\widetilde O(\sqrt d) factor only in the estimation term. For KV cache, each action refreshes a root-to-node path, with coverage determined by the current and preceding MM rounds. Finite-direction approximation reduces optimization to tree-DP subproblems, each costing O~(P(M+1)2)\widetilde O(P(M+1)^2) for a tree of size PP. Including all directions and matrix computations, the cyclic-refresh implementation takes O~(d3+d(M+1)2)\widetilde O(d^3+d(M+1)^2) per replanning call, with regret

O~(dRS(M+1)+σd3/2T).\widetilde O\left(dRS(M+1)+\sigma d^{3/2}\sqrt T\right).

For semantic cache, the disjoint-bundle structure supports sorting under a finite-vertex confidence approximation, followed by cyclic refreshes. The per-call cost is O~(d3+dn)\widetilde O(d^3+dn), where nn is the number of bundles/actions, and the regret is

O~(d(M+1)Δμ+d3/2vUμT+d2κvρ2Δμ).\widetilde O\left(d(M+1)\Delta_\mu+d^{3/2}\sqrt{vU_\mu T}+d^2\kappa v\rho^2\Delta_\mu\right).

⇒\Rightarrow In the revised manuscript, we state the corresponding computational and regret guarantees in Appendices C.6 and C.7 (p. 23, lines 1204–1241; pp. 24–25, lines 1295–1325).

2. Known memory map (W2).

How restrictive is the assumption that the memory map is known? How can such a map be specified or estimated in practice, and what happens when it is only approximately known?

Response: We appreciate this concern regarding the scope of the known memory map. Following prior work on LBM [1, 2], our current framework assumes that the memory map is known. We clarify below when this assumption is reasonable in practice, and then discuss how the framework may be extended when the memory map must instead be estimated or is only approximately known.

First, beyond the KV- and semantic cache problems discussed in our paper, a known memory map can arise naturally in applications such as recommendation and pricing. For example, in recommendation and advertising, AA can encode specified recommendation frequency and recency features based on past exposures, which are recorded by the learner through its own recommendation history, while θ⋆\theta^\star captures unknown user preferences and exposure-response coefficients. Similarly, in dynamic pricing with finite-memory reference price effects, AA can encode a reference price computed from the learner's recent posted prices under a specified rule, while θ⋆\theta^\star captures the unknown effects of the current and reference prices on demand. These examples illustrate settings in which the memory map is known while the reward response remains unknown.

⇒\Rightarrow In the revised manuscript, we have expanded the discussion of the known memory map assumption and its practical interpretation in Section 2, Remark 1 (p. 4, lines 162–174).

Furthermore, when the memory map is unknown, one possible approach is to specify a parametric model and calibrate it using historical logs or controlled experiments. If an estimate A^(⋅)\widehat A(\cdot) satisfies

sup⁡s∥A^(s)−A(s)∥op≤ε,\sup_s\|\widehat A(s)-A(s)\|_{\mathrm{op}}\le\varepsilon,

the induced linear mean reward bias is at most SεS\varepsilon per round. Given this error bound, Algorithm 1 can be extended by enlarging its confidence bounds and optimistic predictions to account for the bias, yielding an additional O~(dSεT)\widetilde O(\sqrt d S\varepsilon T) regret term while preserving the additive memory dependence. This dependence is also consistent with misspecified linear bandit analyses [4]. The additional term is dominated by the leading estimation error when ε=O(1/T)\varepsilon=O(1/\sqrt T). We leave a detailed treatment of estimating unknown memory maps and analyzing the resulting learning problem for future work.

⇒\Rightarrow In the revised manuscript, we have added discussion of possible extensions to unknown memory maps in Section 7 (p. 10, lines 518–524).

[1] Clerici, G., Laforgue, P., & Cesa-Bianchi, N. (2023). Linear bandits with memory: from rotting to rising. Transactions on Machine Learning Research, 2024.

[2] Ann, H., Choi, H., Hwang, T., Shin, Y., Cheong, H., & Oh, M. H. (2026). Generalized Linear Bandits with Memory. International Conference on Machine Learning, 2026.

[3] Munos, R., & Szepesvári, C. (2008). Finite-Time Bounds for Fitted Value Iteration. Journal of Machine Learning Research, 9:815–857.

[4] Lattimore, T., Szepesvári, C., & Weisz, G. (2020). Learning with Good Feature Representations in Bandits and in RL with a Generative Model. International Conference on Machine Learning, 2020.

Thank you for the response; most of my concerns have been addressed. I'd like to keep my score (already is 4).

Thank you for your careful review and constructive feedback. We are glad that our responses and revisions have addressed most of your concerns, and we appreciate your time throughout the discussion.

Reviewer_tMALOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

Building on the bandits with memory settings of Clerici et al. (2023) and Ann et al. (2026), this paper proposes algorithms for linear and generalized linear reward models. Their regret bounds separate the leading dTd\sqrt{T} statistical term from an additive cost depending on the memory length MM; lower bounds show that this memory cost is unavoidable up to logarithmic factors, although a gap remains for an additional curvature term in the generalized model. The paper also evaluates the algorithms on simulated KV and semantic caching tasks motivated by LLM serving.

Critical strengths
  1. The paper achieves a near-optimal regret guarantee by combining the discounted value function Jk(s)J_k(s) with determinant triggered rare switching. Lemma 1 bounds the value difference between any two initial memory states by 2RSM2RSM, while Lemma 2 decomposes regret into an O(KRSM)O(KRSM) memory cost and a reward estimation term. The determinant doubling rule limits the number of policy updates to K=O(dlog⁡T)K=O(d\log T), making the dependence on MM additive rather than coupled with T\sqrt{T}, as in prior bounds. I have reviewed all the proofs and found no apparent issues. This separation is a substantial theoretical contribution.

  2. The paper broadens the practical relevance of Bandits with Memory beyond traditional applications such as recommendation and advertising. In particular, it shows how KV-cache refresh decisions in LLM serving can be formulated within the linear bandits with memory framework to improve the reuse of prefix computations. The experiments further support the applicability of this framework to LLM serving workloads.

Critical weaknesses

I did not identify a major technical weakness in the regret analysis. Efficient planning for arbitrary large memory-state spaces remains open, although this is also a limitation of prior block-based approaches and is acknowledged by the authors.

Questions for authors

Questions

  1. Small-state computation. In the small-state regime, how does the total computational cost of your algorithm, including planning, compare theoretically with Ann et al. (2026)? Is there a regime where your algorithm is provably cheaper?

  2. GLM planning cost. An analysis based on Ht(θ⋆)H_t(\theta^\star), as in Abeille et al. (2021), seems conceivable, but that matrix cannot directly serve as an observable determinant trigger. Your construction addresses this issue, yet uk(s,a)=max⁡θ∈Ckμ(ϕ(s,a)⊤θ)u_k(s,a)=\max_{\theta\in\mathcal C_k}\mu(\phi(s,a)^\top\theta) appears to require a parameter optimization whenever a state-action pair is evaluated. Does computing JkJ_k therefore require such an optimization for every state-action pair? If so, how is this practical when the memory state space grows exponentially, and is there a cheaper equivalent implementation?


For Future Works

  1. Large-state planning. For a general memory map A(s)A(s), is efficient planning in the large-state regime inherently computationally hard, or is its difficulty specific to existing algorithms? Is there a hardness result, and what additional structure on A(s)A(s) would make planning tractable?
6 comments

We sincerely thank the reviewer for recognizing the theoretical contribution, proof correctness, empirical novelty, and technical contribution of the paper.

We also appreciate the reviewer for pointing out several important directions for improvement, including a more detailed discussion of the total computational cost in the small-state regime, the GLBM planning cost, and the computational difficulty of large-state planning. We have revised the manuscript to address these questions through a new computational complexity and hardness analysis (Appendix C.2), expanded discussions (Remark 2), additional details on GLBM planning (Appendix B), and more explicit analyses of structured planning implementations (Appendices C.3, C.6, and C.7). We believe these revisions have substantially improved the clarity and completeness of the manuscript.

We provide the detailed responses to each question below.

1. Small-state computation (Q1).

Question: In the small-state regime, how does the total computational cost of the proposed algorithm, including planning, compare theoretically with [1]? Is there a regime where the proposed algorithm is provably cheaper?

Response: We thank the reviewer for raising this question. Indeed, our approach can offer a computational advantage, particularly in the long-horizon regime.

For linear rewards, using rank-one matrix updates, our algorithm has a total computational cost of O~(d2T+dNeff,1)\widetilde O(d^2T+dN_{\mathrm{eff},1}), while the approach in [1] has a cost of O~(d2T+dT/MNeff,2)\widetilde O(d^2T+\sqrt{dT/M}N_{\mathrm{eff},2}), where Neff,1N_{\mathrm{eff},1} and Neff,2N_{\mathrm{eff},2} denote the respective costs of one planning call. For a finite action set with n=∣A∣n=|\mathcal A|, our planner operates over nMn^M action histories, whereas [1] optimizes over nΘ(MT/d)n^{\Theta(\sqrt{MT/d})} action blocks under its prescribed block length. Thus, our planning domain does not grow with the horizon, providing a computational advantage in the long-horizon regime.

Similarly, for generalized rewards, when using the fast cutting-plane method [2], our approach has a total computational cost of O~(d3T+dNeff,3)\widetilde O(d^3T+dN_{\mathrm{eff},3}) while preserving the regret bound order, whereas the approach in [1] can be implemented with a cost of O~(d3T+T/MNeff,4)\widetilde O(d^3T+\sqrt{T/M}N_{\mathrm{eff},4}) by solving its OMD projections through spectral decomposition and a one-dimensional root search. Here, Neff,3N_{\mathrm{eff},3} and Neff,4N_{\mathrm{eff},4} denote the respective costs of one planning call. The similar comparison holds for the planning domains: for a finite action set with n=∣A∣n=|\mathcal A|, our planner operates over nMn^M action histories, whereas the approach in [1] optimizes over nΘ(MT)n^{\Theta(\sqrt{MT})} action blocks under its prescribed block length. Thus, our planning domain again does not grow with the horizon, providing a computational advantage in the long-horizon regime.

⇒\Rightarrow In the revised manuscript, we have added the total computational cost comparison with prior methods in Appendix C.2 (p. 19, lines 975–996), and summarized the planning domain comparison in Remark 2 (p. 5, lines 247–257).

2. GLBM planning cost (Q2).

Question: While the proposed construction addresses the observable determinant-trigger issue, does computing uk(s,a)u_k(s,a) require a separate parameter optimization for every state-action pair? If so, how practical is this for large memory state spaces, and is there a more efficient implementation?

Response: We thank the reviewer for recognizing that our construction addresses the determinant-trigger issue under generalized rewards. Regarding the optimization of uk(s,a)u_k(s,a), as the confidence set Ck\mathcal C_k remains fixed within each episode, the optimization only needs to be performed once for each (s,a)(s,a) within each episode and reused throughout later rounds in this episode. In the worst case, each (s,a)(s,a) requires a separate optimization at the beginning of an episode. However, since μ\mu is increasing, computing uk(s,a)u_k(s,a) reduces to maximizing the linear prediction ϕ(s,a)⊤θ\phi(s,a)^\top\theta over the convex set Ck\mathcal C_k and then applying μ\mu. Using a fast cutting-plane method [2], each problem can be solved in expected O~(d2T+d3)\widetilde O(d^2T+d^3) time while introducing only O(Δμ/T)O(\Delta_\mu/T) cumulative reward estimation error, which can be absorbed by the regret upper bound in Theorem 3, leaving the regret order unchanged. Hence, this optimization does not introduce additional exponential complexity in the number of memory states in our algorithm, while the main complexity still comes from the planning over action histories, similar to the linear reward case.

⇒\Rightarrow In the revised manuscript, we have added detailed discussions of this GLBM planning step in Appendix B (p. 17, lines 878–887), including the reuse of uk(s,a)u_k(s,a) within each episode, its reduction to linear optimization over Ck\mathcal C_k, and the cutting-plane implementation. The resulting total computational cost is further analyzed in Appendix C.2 (p. 19, lines 985–996).

Regarding more efficient implementations under large-state scenarios, we defer our response to the third question below.

3. Large-state planning.

Question: For a general memory map A(s)A(s), is efficient planning in the large-state regime inherently computationally hard, or is its difficulty specific to existing algorithms? Is there a hardness result, and what additional structure on A(s)A(s) would make planning tractable?

Response: The large-state difficulty is intrinsic rather than specific to our algorithms. While exact planning is computationally hard for general memory maps, we identify a structural condition that enables exact polynomial-time planning, develop efficient application-specific approximations with explicit guarantees, and discuss generic approximation methods for large-state settings.

We first show that exact planning is inherently computationally hard in general, even under full information. For arbitrary bounded memory maps, planning is NP-hard in the linear reward setting even when the reward parameter is known. Consider d=1d=1, A={0,1}\mathcal A=\{0,1\}, and θ⋆=1\theta^\star=1. Given a Boolean formula FF with MM variables, define A(s)=1{s satisfies F}A(s)=\mathbf 1\lbrace s\text{ satisfies }F\rbrace. Any assignment can be reached by executing its MM binary actions, and the optimal discounted value is positive if and only if FF is satisfiable. Thus, deciding whether the optimal value is positive solves SAT. Therefore, unless P=NPP=NP, polynomial-time exact planning cannot be guaranteed in general.

⇒\Rightarrow In the revised manuscript, we have added this hardness result in Appendix C.2 (pp. 18–19, lines 962–974).

Regarding the question about additional structures that make planning tractable, we first identify a structural condition that enables exact polynomial-time planning. All possible action histories may be equivalent to polynomially many “effective” states in nn and MM, as multiple different histories share the same effective state that determines both the reward and the next effective state. This captures the hard-gate memory map in our synthetic experiment in Section 6, which can model production systems with setup delays after switching operating modes. Here, the last action and its consecutive run length, capped at MM, give only O(nM)O(nM) effective states. Bellman planning can therefore operate only on these compressed states without changing the underlying planning problem and obtain polynomial-time computational complexity.

⇒\Rightarrow In the revised manuscript, the exact implementation is described in Appendix C.3 (p. 19-20, lines 998–1029).

We also exploit application-specific structure to obtain efficient approximate planning. For KV cache, each action refreshes a root-to-node path in a known tree, and the reward feature records the components covered by paths refreshed in the current and preceding MM rounds. As described in Appendix C.6, finite-direction approximation and tree dynamic programming can find the best union of at most M+1M+1 paths in O(P(M+1)2)O(P(M+1)^2) time, where PP is the tree size. The disjoint bundles in semantic caching form a simpler special case, for which sorting suffices. These structures give efficient planning approximations, and the resulting implementations introduce only an additional O~(d)\widetilde O(\sqrt d) factor in the estimation error.

⇒\Rightarrow In the revised manuscript, we state the corresponding computational and regret guarantees in Appendices C.6 and C.7 (p. 23, lines 1204–1241; p. 24–25, lines 1295–1325).

For general classes of this problem, many approximation methods can provide more efficient computation, including projected gradient ascent that is used in [1, 3] and our synthetic experiments in Appendix C.4, or methods such as sampled-state fitted value iteration that compute Bellman targets at sampled histories and fit a value approximation instead of enumerating all histories.

⇒\Rightarrow In the revised manuscript, the above discussion is also summarized in the expanded Remark 2 (p. 5, lines 242–269).

[1] Ann, H., Choi, H., Hwang, T., Shin, Y., Cheong, H., & Oh, M. H. (2026). Generalized Linear Bandits with Memory. International Conference on Machine Learning, 2026.

[2] Lee, Y. T., Sidford, A., & Wong, S. C. (2015). A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. IEEE Symposium on Foundations of Computer Science, 2015.

[3] Clerici, G., Laforgue, P., & Cesa-Bianchi, N. (2023). Linear bandits with memory: from rotting to rising. Transactions on Machine Learning Research, 2024.

Thank you for the detailed responses and revisions. Your clarifications have addressed my main computational concerns. For fixed finite nn, MM, and dd, I agree that your planning domain remains independent of TT, supporting an asymptotic advantage over exhaustive block optimization in Ann et al. (2026).

One scope question remains: the problem setup also permits continuous action sets. In this setting, cutting-plane optimization can evaluate uk(s,a)u_k(s,a) for each queried feature, but the finite bound of nM+1n^{M+1} distinct state–action pairs no longer applies. How is the number of distinct feature queries made by a numerical planner accounted for in Neff,3N_{\mathrm{eff},3}, and what scope is intended for the computational comparison in continuous action spaces?

Reviewer_33xROpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies linear bandits with memory, where the expected reward depends on the current action and the previous MM actions through a known matrix-valued memory map. The unknown reward parameter must be learned while accounting for how current decisions affect future rewards. Performance is measured by policy regret against the optimal complete action sequence over the horizon, starting from the same initial memory.

The authors propose RSM-LinUCB, which combines optimistic reward estimation, discounted Bellman planning, and determinant-triggered policy updates. The analysis exploits the fact that two memory states become identical after executing the same MM actions. This bounds the cost of each policy change and yields a high-probability regret bound of O~(dRS(M+1)+σdT).\widetilde O\left(dRS(M+1)+\sigma d\sqrt T\right). The authors establish a matching minimax lower bound under the stated horizon conditions, extend the approach to generalized linear rewards, and evaluate the algorithms on synthetic problems and two cache applications constructed from real datasets.

Critical strengths
  1. The additive dependence on the memory length is a meaningful theoretical improvement. The regret bound separates the memory cost from the leading statistical learning term, rather than allowing memory to multiply the square-root dependence on the horizon. The explicit dependence on the reward scale RSRS and noise scale σ\sigma further clarifies the different sources of regret.

  2. The Bellman analysis provides a clear explanation for the improved rate. Executing the same MM actions removes the difference between any two initial memory states, which bounds the span of the optimistic value function. Combining this observation with infrequent policy updates limits the total cost of memory. This gives an interpretable mechanism behind the result and a useful analytical approach for problems with finite memory.

  3. The matching lower bound strengthens the main theoretical contribution. The upper bound competes with the optimal full action sequence, which can deliberately shape the memory state to improve future rewards. The memory-dependent lower-bound construction explains why establishing informative memory states can require an unavoidable exploration cost. Together with the statistical lower bound, this establishes the minimax dependence on the main parameters in the linear setting.

  4. The framework accommodates a broad class of known memory effects. The analysis allows arbitrary bounded matrix-valued memory maps, including order-sensitive effects and interactions among past actions. The generalized linear extension further broadens the scope and preserves an additive memory contribution while addressing the difficulties introduced by link-function curvature.

  5. The experimental evaluation covers several complementary settings, including synthetic instances, continuous actions, and two applications derived from real datasets. The construction of exact comparators for the structured cache instances is particularly useful, since computing the optimal policy-regret benchmark can itself be difficult. The reported improvements across these settings provide encouraging evidence for the approach.

Critical weaknesses
  1. The general regret guarantee does not establish computational tractability. With nn discrete actions, the memory state space can contain nMn^M states, making exact Bellman planning exponential in the memory length. Appendix C discusses approximate planning through policy iteration, but this does not remove the state-space dependence, and the sufficient iteration budget for a small regret penalty also scales with the horizon. The efficient implementations used in the experiments exploit additional structure that is not available for an arbitrary bounded memory map. Thus, the statistical result is strong, but the distinction between the general planning-oracle guarantee and computationally tractable special cases should be made more explicit.

  2. Several experimental implementations differ substantially from the algorithm covered by the main theorem. The theoretical discount factor is γ=1−1/T\gamma=1-1/T, whereas the experiments use other values. The continuous-action implementation restricts planning to periodic sequences and uses a finite number of gradient steps, without a general guarantee for the resulting approximation error. The cache implementations also approximate optimistic planning; although the appendix discusses their guarantees, these introduce an additional O~(d)\widetilde O(\sqrt d) statistical factor. Consequently, the empirical results support the practical variants more directly than the precise algorithm and regret rate established in the main theorem. Comparisons with exact planning on small instances and sensitivity studies for the discount factor and planning budget would help clarify this connection.

  3. The generalized linear regret bound contains an unmatched curvature-dependent term. Specifically, the upper bound includes d2κvρ2Δμd^2\kappa v\rho^2\Delta_\mu, while the lower bound matches only the memory and leading statistical contributions. Although this additional term is independent of the horizon, it can dominate over relevant horizons when the minimum link-function slope is small and κ\kappa is large. The authors acknowledge this limitation, but it means that the near-optimality conclusion is stronger for the linear setting than for the full generalized linear setting. A clearer characterization of when the curvature term becomes negligible would help assess the scope of the extension.

Questions for authors
  1. Under what additional assumptions on the memory map can the planning step be implemented in time polynomial in the dimension and memory length? Can the authors distinguish more explicitly between the general oracle-based result and the guarantees available for tractable special cases?

  2. How does using the experimental discount factors instead of γ=1−1/T\gamma=1-1/T affect the regret guarantee? Can the authors provide a sensitivity study or an explicit bound for the additional error?

  3. Can comparisons with exact Bellman planning on small instances quantify the effects of periodic-policy restrictions, limited numerical optimization, and approximate optimism? Can the resulting regret guarantees for the cache implementations, including the additional dimension dependence, be stated alongside their empirical results?

  4. Is the curvature-dependent term in the generalized linear bound necessary, or could it be reduced through a sharper analysis? For representative link functions, can the authors characterize the horizon beyond which this term is smaller than the leading statistical contribution?

3 comments

We sincerely thank the reviewer for recognizing our contribution on novel analysis, matching lower bound, and empirical validation.

We agree that computational tractability, the differences between the theoretical algorithm and the numerical implementations, and the curvature dependence, all warrant further clarification. We have revised the manuscript to address these suggestions through: a new hardness result and computational analysis (Appendix C.2), expanded discussions (Remark 2 and the discussion following Theorem 4), and additional ablation studies (Appendix C.5). We greatly appreciate the constructive feedback, which has helped us substantially improve the clarity and completeness of the manuscript.

We provide the detailed responses to each question below.

1. Computational tractability (W1 & Q1).

Question: Under what additional assumptions on the memory map can the planning step be implemented in time polynomial in the dimension and memory length? Can the authors distinguish more explicitly between the general oracle-based result and the guarantees available for tractable special cases?

Response: Computational tractability is indeed a central challenge for the planning step and was one motivation for Remark 2 in our initial submission. To summarize, this planning is inherently computationally hard even under the full information, we provide two generic approximation approaches, identify conditions that enable exact polynomial-time planning, and develop application-specific structured approximations with explicit regret guarantees.

First, this computational intractability is inherent in this class of problems and is not specific to our learning algorithm: even when θ⋆\theta^\star is known, computing the optimal discounted value under a general memory map is NP-hard. Thus, polynomial-time exact planning cannot be guaranteed in general unless P=NPP=NP.

⇒\Rightarrow In the revised manuscript, we have added this hardness argument in Appendix C.2 (pp. 18–19, lines 960–996).

Although exact planning is computationally intractable in general, our approach enjoys a computational advantage over existing learning approaches. The existing approaches to LBM require planning over nM+Ln^{M+L} candidate action blocks, where the prescribed total block length M+LM+L scales as T1/4T^{1/4} in [1] and T1/2T^{1/2} in [2]. In comparison, our planner operates over nMn^M memory states, whose number is independent of TT. Furthermore, our algorithm is equipped with a rare-switching component that also limits planning to O~(d)\widetilde O(d) episodes.

⇒\Rightarrow In the revised manuscript, we have expanded this comparison in Remark 2 (p. 5, lines 246–255), with total cost details provided in new Appendix C.2 (pp. 18–19, lines 960–996).

We provide two general approximation approaches for the planning. For small state spaces, discounted Howard policy iteration computes JkJ_k near-exactly. We show in Theorem 5 in Appendix C.1 that an O(Tlog⁡T)O(T\log T) iteration budget preserves the regret order. For larger problems, projected gradient ascent provides a practical approximation. This approach was also used in [1, 2] and discussed in our initial submission (see Appendix C.4 in the revised manuscript).

⇒\Rightarrow In the revised manuscript, we have clarified these approximation techniques in Remark 2 (p. 5, lines 246–258).

We also characterize structural conditions when tractable exact planning is achievable. One sufficient condition is when different action histories admit polynomially many effective states that determine both the reward feature and the next effective state after any action. Information matrix updates and factorizations cost O(d2)O(d^2) and O(d3)O(d^3), respectively, which are polynomial in dd. The hard-gate memory map in experiments in Section 6 tracks only the last action and its consecutive run length, giving only O(nM)O(nM) states with n=∣A∣n=|\mathcal A| denoting the size of action set, modeling applications in setup delays after switching operating modes. A direct implementation retains Theorem 1's regret bound and takes polynomial time of O~(d3+nd2+n2M)\widetilde O(d^3+nd^2+n^2M) per replanning call.

⇒\Rightarrow In the revised manuscript, we have clarified the condition and highlighted this example in Remark 2 (p. 5, lines 259–269). The exact implementation is described in Appendix C.3 (p. 19-20, lines 998–1029).

We further exploit the structural properties in KV-cache and semantic cache applications in our experiments, and develop dedicated polynomial-time replanning approximation with an additional O~(d)\widetilde O(\sqrt d) factor only in the estimation term. For KV cache, each action refreshes a root-to-node path, with coverage determined by the current and preceding MM rounds. Finite-direction approximation reduces optimization to tree-DP subproblems, each costing O(P(M+1)2)O(P(M+1)^2) for a tree of size PP. Including all directions and matrix computations, the cyclic-refresh implementation takes O~(d3+d(M+1)2)\widetilde O(d^3+d(M+1)^2) per replanning call, with regret

O~(dRS(M+1)+σd3/2T).\widetilde O\left(dRS(M+1)+\sigma d^{3/2}\sqrt T\right).

For semantic cache, the disjoint-bundle structure supports sorting under a finite-vertex confidence approximation, followed by cyclic refreshes. The per-call cost is O~(d3+dn)\widetilde O(d^3+dn), where nn is the number of bundles/actions, and the regret is

O~(d(M+1)Δμ+d3/2vUμT+d2κvρ2Δμ).\widetilde O\left(d(M+1)\Delta_\mu+d^{3/2}\sqrt{vU_\mu T}+d^2\kappa v\rho^2\Delta_\mu\right).

⇒\Rightarrow In the revised manuscript, we state these regret bounds explicitly in Appendices C.6 and C.7 (p. 23, lines 1240–1241; p. 25, lines 1325–1326), alongside the existing planning analyses in both appendices.

2. Experimental implementations and additional experiments (W2 & Q2 & Q3).

Questions: (i) How is the experimental discount factor γ\gamma chosen and how does it affect the regret guarantee? (ii) How sensitive are the results to the planning budget? (iii) How do approximate planners compare with exact Bellman planning, and what guarantees apply to the cache implementations?

Response: We appreciate the reviewer pointing out these directions to help us further improve the clarity of our numerical validations. We provide all the implementation details in Appendices C.4, C.6, and C.7, and we added extra ablation studies in Appendix C.5 (pp. 20–21, lines 1072–1119). All ablation experiments use d=10d=10, R=S=1R=S=1, T=106T=10^6, σ=0.25\sigma=0.25, λ=0.625\lambda=0.625, and δ=0.05\delta=0.05, with the same θ⋆\theta^\star as in our synthetic experiments.

(i) Discount factor γ\gamma. We thank the reviewer for highlighting the differences between the theoretical algorithm and its numerical implementations. Under exact optimistic planning, the theoretical setting γ=1−1/T\gamma=1-1/T can be extended to γ=1−c/T\gamma=1-c/T for any fixed constant c>0c>0 with T>cT>c, without changing the regret order. Specifically, the memory term in Lemma 2 changes from 2(K+2)RSM2(K+2)RSM to at most 2(K+c+1)RSM2(K+c+1)RSM, where K=O(dlog⁡T)K=O(d\log T), while the reward estimation bound remains unchanged. For the discount ablation, we use the hard-gate setting in Section 6 with M=100M=100 and set γ=1−c/T\gamma=1-c/T, where c∈{1,10,20,…,100}c\in\{1,10,20,\ldots,100\}. The mean regret changes little across the tested values of cc.

ccRegret at T=106T=10^6
13746.76±37.393746.76\pm37.39
103748.21±89.693748.21\pm89.69
203751.40±101.253751.40\pm101.25
303753.36±81.353753.36\pm81.35
403755.64±100.133755.64\pm100.13
503757.64±65.103757.64\pm65.10
603759.98±50.733759.98\pm50.73
703762.53±84.913762.53\pm84.91
803765.17±54.503765.17\pm54.50
903767.03±27.913767.03\pm27.91
1003768.86±20.103768.86\pm20.10

(ii) Planning budget. Our adoption of projected gradient ascent under continuous action sets and an additive memory map in Appendix C.4 follows prior work on LBM [1, 2]. The experiments show that our algorithm outperforms these baselines under this common setting. For the planning-budget ablation, we use the same continuous-action setting with M=100M=100 and γ=0.999\gamma=0.999, varying the iteration budget from 60 to 300 in increments of 60. Increasing the budget yields modest reductions in mean regret, with little further improvement under large planning budgets.

nitn_{\mathrm{it}}Regret at T=106T=10^6
606763.41±969.066763.41\pm969.06
1206606.26±1070.976606.26\pm1070.97
1806452.11±1068.076452.11\pm1068.07
2406335.17±859.836335.17\pm859.83
3006332.63±1103.236332.63\pm1103.23

(iii) Exact versus approximate planning. We agree that the empirical gap between the exact and approximate planning is important and to quantify it, we added a direct comparison on small-scale instances. We have the results ready and have added them to the revised manuscript. To compare planning methods on small-scale instances, we use the same additive memory map with M=3M=3, γ=0.999\gamma=0.999, and an action set containing five unit-norm actions generated by normalizing Gaussian vectors. We compare exact Bellman planning, exact optimization over period-MM action sequences, and gradient-based periodic planning, projecting each updated action onto the nearest available action. Both exact and gradient-based periodic planning achieve performance close to exact Bellman planning throughout the tested horizon. In addition, for the regret guarantees of the cache approximation implementations in Section 6, please refer to our response to the first question.

t/105t/10^5Exact BellmanExact periodicGradient-based periodic
1195.80±14.72195.80\pm14.72196.12±16.17196.12\pm16.17202.22±11.88202.22\pm11.88
2284.76±21.69284.76\pm21.69288.94±18.70288.94\pm18.70292.81±33.64292.81\pm33.64
3373.36±25.74373.36\pm25.74376.87±25.84376.87\pm25.84377.97±36.70377.97\pm36.70
4439.65±32.03439.65\pm32.03445.56±32.56445.56\pm32.56439.32±32.57439.32\pm32.57
5498.60±40.63498.60\pm40.63501.53±38.33501.53\pm38.33512.51±34.59512.51\pm34.59
6550.10±25.87550.10\pm25.87551.59±24.53551.59\pm24.53580.16±42.77580.16\pm42.77
7602.05±28.11602.05\pm28.11603.55±31.33603.55\pm31.33624.06±52.04624.06\pm52.04
8650.54±78.83650.54\pm78.83650.60±69.99650.60\pm69.99668.56±75.03668.56\pm75.03
9680.51±76.19680.51\pm76.19686.27±66.99686.27\pm66.99701.87±78.41701.87\pm78.41
10726.90±70.44726.90\pm70.44740.43±63.25740.43\pm63.25748.17±83.46748.17\pm83.46

3. Curvature term dependence (Q4).

Question: Is the curvature-dependent term in the generalized linear bound necessary, or could it be reduced through a sharper analysis? For representative link functions, can the authors characterize the horizon beyond which this term is smaller than the leading statistical contribution?

Response: Our analysis suggests that some curvature-dependent identification cost can be inherent in the general setting. Intuitively, in regions where the mean reward changes little with the linear prediction, different parameter values can produce similar observations. The learner may therefore need more samples to distinguish them, requiring additional exploration before the local curvature can be reliably accounted for. Specifically, for the widely studied logistic reward function, existing lower bound constructions show that additional dependence on nonlinearity or action geometry cannot be uniformly removed in the worst case [3, 4, 5]. For general reward functions, however, a tight lower bound characterizing the precise curvature-induced cost still remains as an interesting open direction.

Furthermore, ignoring logarithmic factors, the curvature term is dominated by the leading statistical term once T≳d2κ2vρ4Δμ2/UμT\gtrsim d^2\kappa^2v\rho^4\Delta_\mu^2/U_\mu. It is also absorbed by the memory term when M≳dκvρ2M\gtrsim d\kappa v\rho^2. For many commonly studied reward models, the main link-dependent factors governing the curvature term are κ\kappa and Δμ\Delta_\mu. For example, under the widely studied logistic reward model, v=ρ=1v=\rho=1 and Δμ≤1\Delta_\mu\le1, so κ\kappa is the main potential contributor in the curvature term. For Poisson rewards, v=ρ=1v=\rho=1 as well, but both κ\kappa and Δμ\Delta_\mu grow with the prediction range RSRS and contribute to the size of the curvature term. When these quantities are moderate and the curvature term is absorbed under the conditions above, our regret bound in Theorem 3 remains near-optimal.

⇒\Rightarrow In the revised manuscript, we have expanded the discussion of the curvature-induced identification cost following Theorem 4 in Section 5 (pp. 8–9, lines 426–434) and highlighted the remaining gap in the Conclusion (p. 10, lines 516–524).

[1] Clerici, G., Laforgue, P., & Cesa-Bianchi, N. (2023). Linear bandits with memory: from rotting to rising. Transactions on Machine Learning Research, 2024.

[2] Ann, H., Choi, H., Hwang, T., Shin, Y., Cheong, H., & Oh, M. H. (2026). Generalized Linear Bandits with Memory. International Conference on Machine Learning, 2026.

[3] Jun, K.-S., Jain, L., Mason, B., & Nassif, H. (2021). Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits. International Conference on Machine Learning, 2021.

[4] Dong, S., Ma, T., & Van Roy, B. (2019). On the Performance of Thompson Sampling on Logistic Bandits. Conference on Learning Theory, 2019.

[5] Boudart, P., Gaillard, P., & Rudi, A. (2026). Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm. International Conference on Algorithmic Learning Theory, 2026.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.