A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-Buy

Motivated by context management in LLM agents, this paper studies a repeated rent-or-buy model with schedule-independent history growth and a fixed reset cost K. When the growth consists of P constant runs, the classical threshold rule incurs a total cost at most (2P − 1)K above the optimal schedule chosen with hindsight. This additive bound is sharp and does not depend on the session length. The proof uses potentials derived from the relative value functions of the constant-growth problems. For sessions with at most two runs, the optimal worst-case additive bound among deterministic rules is 2K. A variant that also resets when growth decreases achieves this bound, while the threshold rule can lose arbitrarily close to 3K. The paper also extends the analysis to approximately piecewise-constant growth. This manuscript is a preprint.