- 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 , 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
-
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.
-
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
-
Computational tractability of the Bellman planning step remains a limitation. In the general formulation, the memory state space is , 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.
-
The assumption that the memory map 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
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, can encode specified recommendation frequency and recency features based on past exposures, which are recorded by the learner through its own recommendation history, while captures unknown user preferences and exposure-response coefficients. Similarly, in dynamic pricing with finite-memory reference price effects, can encode a reference price computed from the learner's recent posted prices under a specified rule, while 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.
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 satisfies
the induced linear mean reward bias is at most 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 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 . We leave a detailed treatment of estimating unknown memory maps and analyzing the resulting learning problem for future work.
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.
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 Jk near-exactly. We show in Theorem 5 in Appendix C.1 that an O(TlogT) 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.
⇒ 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) states with n=∣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) per replanning call.
⇒ 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) 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 M rounds. Finite-direction approximation reduces optimization to tree-DP subproblems, each costing O(P(M+1)2) for a tree of size P. Including all directions and matrix computations, the cyclic-refresh implementation takes O(d3+d(M+1)2) per replanning call, with regret
O(dRS(M+1)+σd3/2T).
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), where n is the number of bundles/actions, and the regret is
O(d(M+1)Δμ+d3/2vUμT+d2κvρ2Δμ).
⇒ 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).