When a recommender shows a user the same song, creator, or product category, interest drops right after the exposure and then slowly comes back. How much interest has returned depends on how long the system waits before showing the item again. This note proposes to learn these "recovery curves" online, under one assumption: interest returns with diminishing gains. The curve rises quickly after a rest and then levels off, which makes it a concave, non-decreasing function of the time since the last exposure. That single shape assumption buys two things. First, the best long-run spacing of repeated exposures becomes an easy convex optimization problem instead of a combinatorial one. Second, the system can put a guaranteed ceiling on how good a long rest would be without ever trying that rest, because a concave curve always lies below its tangent lines.
The opportunity sits between two existing lines of work on bandits, which are sequential decision problems where a learner repeatedly picks an action (an "arm") and observes a noisy reward. Satiation bandits either fix a specific parametric recovery law or allow arbitrary recovery curves. The first risks being wrong when real users forget differently. The second pays a steep statistical price. Concave-bandit theory shows that concavity breaks regret barriers, but only for rewards that rise forever. We move concavity into the regime where it naturally belongs for preference drift: the rebound phase of a satiate-and-recover cycle.
Core Claim
Model each arm $a$ by an unknown recovery curve $\mu_a(\tau)$, the expected reward of showing arm $a$ after it has rested for $\tau$ rounds, assumed bounded, non-decreasing, and concave in $\tau$. Each pull resets the arm's rest clock to zero. Suppose arm $a$ is shown in a fraction $f_a$ of rounds with even spacing, so that it is shown every $1/f_a$ rounds. The long-run average reward is then
$$ R(f) = \sum_a f_a\,\mu_a(1/f_a), \qquad \sum_a f_a = 1,\; f_a \ge 0 . $$
Each term $f\,\mu(1/f)$ is what convex analysis calls the perspective of $\mu$, and it is concave in $f$ whenever $\mu$ is concave. So the fluid version of the scheduling problem is a concave maximization over the simplex. For a fixed number of exposures, Jensen's inequality says equal gaps beat unequal ones, so even spacing is optimal within each arm.
Our claims are threefold. This planning problem can be solved exactly in its relaxed form and rounded to an integer schedule with a measurable loss. Shape-constrained confidence envelopes on $\mu_a$ let an optimistic learner explore few rest lengths per arm. The resulting regret, measured against the best periodic schedule, should be strictly better than the $\widetilde{O}(KT^{3/4})$ available for unconstrained recovery curves. We also claim the method is more robust than parametric methods when the true forgetting law is not exponential.
Relation to Prior Work
Three papers motivate the gap by modeling satiation and recovery without concavity. Rebounding Bandits for Modeling Satiation Effects models satiation as a linear dynamical system in which a hidden state rises with pulls and decays geometrically during rest. It estimates the parameters by least squares, plans with a lookahead integer program, and proves $O(T^{2/3})$ regret. It also shows that cyclic, variety-seeking schedules are optimal for identical arms, a result it connects to Max-$K$-Cut. Its single-exposure recovery curve, $b-\lambda\gamma^\tau s_0$, is itself concave and increasing in $\tau$. Our model is therefore a nonparametric relaxation of the one-exposure case of theirs. We give up their multi-pull satiation memory, and in return we do not need the forgetting law to be geometric.
Break your Bandit Routine with LSD Rewards allows arbitrary reward curves as a function of time since the last switch. It needs a calibration pull to reset each arm's history and reaches $\widetilde{O}(KT^{3/4})$ regret through expensive block-based combinatorial planning. We restrict the recovery side of their model to concave curves in exchange for a convex planning problem and, we conjecture, a better exponent.
Ads that Stick pairs a concave exposure gain with a convex annoyance term that decays exponentially. It solves the scheduling problem with known parameters and explicitly leaves online learning open. It also finds that uniform spacing is suboptimal, with optimal ads clustering near session endpoints. This might seem to contradict our even-spacing result, but it does not. Their suboptimality comes from finite sessions, where the endpoints are special, and from a gain that depends on exposure count. Our result is about long-run spacing between repeats of the same item. We will check the finite-horizon edge effects directly rather than assume them away.
Two lines of work supply the method. Tightening Regret Lower and Upper Bounds in Restless Rising Bandits shows that concavity lowers the regret lower bound for restless rising rewards from $\Omega(T^{2/3})$ to $\Omega(T^{3/5})$, with an $\widetilde{O}(T^{7/11})$ algorithm. This is evidence that concavity has real statistical value, but their result is restricted to rewards that only ever rise. Tight Policy Regret Bounds for Improving and Decaying Bandits and Mitigating Disparity while Maximizing Reward use tangent-line extrapolation as an optimistic ceiling for concave, pull-driven improvement. We reuse that tangent trick, but apply it along the rest-time axis, which the learner controls by choosing when to revisit. We do not apply it along the pull-count axis. Addressing the Long-term Impact of ML Decisions via Policy Regret fits best-case concave curves to noisy data with a linear program. We borrow that fitting step, and we note that it provides no noisy-regime guarantee, which we aim to supply.
Finally, the recency-weighted preference learning in Right Now, Wrong Then treats drift as something to down-weight, not something to plan around. It is a reference point for "track, don't model", not a competitor on this problem.
Research Program
The work has three parts.
The first part is the planner. We solve the concave frequency program with a generic convex solver, or by water-filling on the derivatives of the perspective function. We then round the frequencies to an integer schedule using a deficit-based rule that serves the arm furthest behind its target spacing. We will bound the rounding loss as a function of the curvature of $\mu_a$ and of how coprime the target periods are, and we will measure that loss empirically against exact dynamic programming on small instances.
The second part is the learner. For each arm we keep noisy observations of the reward at the rest lengths that have actually occurred. The lower envelope interpolates by chords, since a concave function lies above its chords. The upper envelope extends neighboring secant slopes beyond each observed point, since a concave function lies below the continuation of its secants. The optimistic curve is the least concave majorant of the upper confidence limits, which keeps it concave so that the planner stays convex. The algorithm replans on a doubling schedule, as an optimistic analogue of Explore-Estimate-Plan. A key point is that choosing a longer rest is itself exploration of that rest length. The algorithm therefore explores by occasionally stretching gaps, not by making pulls it would otherwise avoid.
The third part is theory. We aim to prove a regret bound against the best periodic schedule with exponent strictly below $3/4$, and a matching-style lower bound for the concave recovery class. The intuition for the exponent is this. Without smoothness assumptions, piecewise-linear interpolation of a bounded concave curve has error that shrinks with grid spacing. Concavity also removes the need to probe rest lengths beyond the tangent-bounded region. We expect a rate between the $T^{3/5}$ and $T^{2/3}$ exponents seen in the concave rising setting, but we state this as a target, not a result.
The scope is deliberately narrow. Arms do not interact, and satiation memory older than the last pull is ignored. Cross-item spillover, which Rebounding Bandits flags as open, is left to follow-up work.
Baselines
The naive reference points are round-robin cycling and myopic greedy, meaning always show the arm with the highest current estimated reward. Greedy is included because Tight Policy Regret Bounds for Improving and Decaying Bandits proves it near-optimal under pure decay. Rebounding Bandits documents its "greedy trap" once rebound matters. Beating greedy is the minimum bar, and it should hold by a growing margin as the horizon grows.
The strongest parametric competitor is Explore-Estimate-Plan from Rebounding Bandits, run with the same horizon, the same total exploration budget, and its lookahead depth tuned on held-out simulator seeds with the same number of tuning trials we give our method. When the true dynamics are geometric, it has a correctly specified model and should win or tie. We count our method as beating it only if we (a) lose by at most a small constant factor in cumulative regret on geometric instances and (b) win clearly on instances with power-law or hyperbolic forgetting and saturating recovery.
The strongest nonparametric competitor is ISI-CombUCB1 from Break your Bandit Routine with LSD Rewards. It gets the same rest-length discretization and a block-length grid tuned under the same budget. Beating it means lower regret at every horizon tested and a fitted log-log regret slope that is visibly smaller. A simpler generic competitor is sliding-window UCB over (arm, rest-length bucket) pairs, with window and bucket width tuned identically.
Two ablations isolate the key ingredient. The first keeps our planner and learner but imposes only monotonicity, so the upper envelope is flat beyond the last observation instead of tangent-extrapolated. The second removes shape constraints entirely and uses per-bucket confidence intervals. If the monotone-only ablation matches the full method, concavity is not doing the work and the claim fails.
The oracle is the best periodic schedule computed with the true curves. It defines regret and also measures the rounding loss.
Reported numbers are thin. The file lists only theoretical rates for these algorithms: $O(T^{2/3})$ for Explore-Estimate-Plan and $\widetilde{O}(KT^{3/4})$ for ISI-CombUCB1. No reported result was found on Lacuna for any recovery-curve bandit on KuaiRand or MIND. The only empirical spacing number available is from Ads that Stick: in their own synthetic ad simulation, their optimal schedule outperforms uniform spacing in total reward by "at least 10%" at sensitivity $\delta\approx0.98$. All other baseline numbers will be produced by us under matched budgets.
Why not just…?
Why not just use the parametric rebounding model? If users forget geometrically, it is the right model, and our method should only match it. The risk is misspecification. Memory research in other fields often finds power-law forgetting, and a geometric fit to a power-law curve will overestimate or underestimate long-rest value in a structured, non-vanishing way. The misspecification sweep in our experiments settles this directly. If Explore-Estimate-Plan with a geometric model stays competitive on power-law instances, the nonparametric generality is not worth its cost, and we would say so.
Why not fit a flexible parametric family and pick the best by validation? This is the most serious threat. Fitting exponential, power-law, and hyperbolic laws and choosing by held-out likelihood may capture most of the benefit with simpler machinery. We include it as an additional baseline with the same planner. Our advantage should appear when the true curve falls outside all three families, for example with a piecewise saturating recovery. We do not predict an advantage inside those families.
Why not use a generic non-stationary bandit, such as a sliding window or ISI-CombUCB1? These methods adapt to any curve, but in doing so they give up the tangent bound that lets a learner rule out long rests without trying them. The concave rising-bandit results in Tightening Regret Lower and Upper Bounds in Restless Rising Bandits show that exactly this kind of structure changes the regret exponent. The monotone-only ablation tests whether the same holds for recovery curves.
Why not just use frequency caps or uniform spacing? For a single arm, even spacing is in fact what our planner recommends, so uniform spacing is not wrong in form. What it misses is choosing a different period for each arm. Round-robin, and a tuned frequency cap searched on a grid under the same budget, measure how much the learned per-arm allocation adds.
Proposed Experiments
Synthetic study. We generate $K\in\{5,20,50\}$ arms whose recovery curves are drawn from geometric, power-law, hyperbolic, and piecewise-linear-saturating families, plus a deliberately non-concave S-shaped family with a refractory delay. We report cumulative regret against the periodic oracle for horizons from $10^3$ to $10^6$, together with fitted regret exponents and planner rounding loss.
Semi-synthetic study on real data. Using KuaiRand, whose randomly exposed videos reduce selection bias in estimating re-engagement, we estimate empirical recovery curves per creator or category. Each curve is the engagement rate as a function of the gap since the user's last exposure to that creator or category. We then drive a simulator from these curves. The Microsoft News Dataset, used in A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems, provides a second, news-category variant.
The decisive checks. There are three.
The first is whether empirical recovery curves in KuaiRand are concave at all. We test this by comparing a concave fit against a monotone isotonic fit on held-out data. If most curves show an S-shaped onset, the core assumption fails in practice. We would then evaluate the fallback of concavity after a learned onset point.
The second is whether the full method beats the monotone-only ablation. If it does not, concavity is not what drives the gains.
The third is whether the method beats validated parametric fitting on the real-data-derived curves, not just on synthetic curves we designed to be off-model. A win on all three would establish concave recovery as a practical middle ground between parametric satiation models and assumption-free ones. A loss on the first or third would be a useful negative result about how human preferences actually rebound.
References
- Rebounding Bandits for Modeling Satiation Effects
- A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits
- Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
- Tightening Regret Lower and Upper Bounds in Restless Rising Bandits
- Tight Policy Regret Bounds for Improving and Decaying Bandits
- Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits
- Addressing the Long-term Impact of ML Decisions via Policy Regret
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- KuaiRand: An Unbiased Sequential Recommendation Dataset with Randomly Exposed Videos
- A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems