PaperlayerView exact revision on arXiv

Source-linked AI summary

Rotting Bandits

Nir Levine, Koby Crammer, Shie Mannor

arXiv:1702.07274v4stat.MLcs.LG

TL;DR

Rotting Bandits address MAB settings where expected rewards decline with repeated pulls, unlike the stationary or quasi-stationary setting commonly studied. The paper develops algorithms and guarantees for cases with and without prior knowledge; simulations report different leading algorithms depending on prior knowledge.

  • Problem

    Most prior MAB work assumes stationary or quasi-stationary rewards, while some motivated settings have expected rewards that decrease with repeated pulls and can require minimizing policy regret.

    Source: §1 · pp. 1–2

  • Method

    The paper studies Rotting Bandits with positive non-increasing rewards and develops algorithms and guarantees for non-parametric and parameterized decay, including model detection in the latter case.

    Source: Assumption 4.3. (D-Detection ability) · p. 5, §7 · pp. 8–9

  • Results

    Without prior knowledge, wSWA consistently and significantly outperformed benchmark algorithms; with prior knowledge, CTOSIM or D-CTOUCB-SIM outperformed all others, including wSWA.

    Source: §5 · p. 7

  • Takeaways & Limitations

    Because Rotting Bandits is novel and lacks suitable available benchmarks, the paper also serves as a benchmark for the setting.

    Source: §7 · p. 9

    The authors identify a lower bound for the non-parametric case and continuous parameterization of the parametric case as future-work directions.

    Source: §7 · p. 9

Abstract

from arXiv · show

The Multi-Armed Bandits (MAB) framework highlights the tension between acquiring new knowledge (Exploration) and leveraging available knowledge (Exploitation). In the classical MAB problem, a decision maker must choose an arm at each time step, upon which she receives a reward. The decision maker's objective is to maximize her cumulative expected reward over the time horizon. The MAB problem has been studied extensively, specifically under the assumption of the arms' rewards distributions being stationary, or quasi-stationary, over time. We consider a variant of the MAB framework, which we termed Rotting Bandits, where each arm's expected reward decays as a function of the number of times it has been pulled. We are motivated by many real-world scenarios such as online advertising, content recommendation, crowdsourcing, and more. We present algorithms, accompanied by simulations, and derive theoretical guarantees.

1 Introduction

Classical MAB work typically assumes stationary or quasi-stationary reward distributions, but Rotting Bandits model expected rewards that decline with repeated pulls. The paper introduces this setting and develops algorithms and theoretical guarantees for cases with and without prior knowledge of the decay.

1 Introduction

  • Classical MAB frames exploration versus exploitation as choosing among fixed arms to maximize cumulative expected reward, and regret measures the gap from the full-information optimum.The introduction notes that prior MAB work commonly assumes stationary or quasi-stationary reward distributions.Source: §1 · p. 1
  • MAB formulations have also been used to model online advertising, packet routing, and online auctions.The cited examples are from Pandey et al. [2007], Awerbuch and Kleinberg [2004], and Kleinberg and Leighton [2003].Source: §1 · p. 1
  • Expected rewards that decline with repeated pulls define Rotting Bandits, a variant motivated by advertising, content recommendation, and crowdsourcing.The introduction cites ad effectiveness, article click-through-rate decay, and declining performance on perception-based tasks as examples.Source: §1 · p. 2
  • In Rotting Bandits, the optimal arm can change, so the paper targets the harder problem of minimizing policy regret.The introduction contrasts this with the stationary case, where an optimal policy always chooses a specific arm.Source: §1 · p. 2
  • The paper presents an easy-to-follow algorithm with theoretical guarantees for the general case and refines guarantees when prior knowledge of rotting models is available..Source: §1 · p. 2

2 Model and Preliminaries

The model assigns each arm a reward distribution whose mean depends on how many times that arm has been pulled. It considers expected total reward and the equivalent regret objective, assumes positive non-increasing means, and establishes the paper’s defined πmax as optimal.

2 Model and Preliminaries

  • At an arm’s nth pull, the agent receives a time-independent σ^2-sub-Gaussian reward with mean µ_i(n).There are K arms, and one arm is pulled at each time step.Source: §2 · p. 2
  • The paper considers both no-prior-knowledge and prior-knowledge cases; in the latter, the mean has an unknown constant part and a rotting part from a known model set.The no-prior-knowledge case assumes only the rotting condition.Source: §2 · p. 2
  • The objective is to maximize expected total reward over horizon T, with regret also treated as an equivalent objective.The passage introduces policies as sequences of arm choices.Source: §2 · p. 2
  • The rotting assumption requires every arm’s expected reward to be positive and non-increasing in its pull count..Source: §2 · p. 2

2.1 Optimal Policy

  • Lemma 2.1 establishes the paper’s defined πmax as an optimal policy for Rotting Bandits, with ties broken randomly..Source: §2.1 · p. 3

3 Non-Parametric Case

For the non-parametric case, the paper introduces Sliding-Window Average (SWA), which uses empirical averages to limit repeated sampling of significantly sub-optimal arms. It also wraps SWA in a doubling trick when the horizon is unknown.

3 Non-Parametric Case

  • SWA uses a windowed empirical average to distinguish significantly sub-optimal arms after enough pulls, bounding how often they are sampled relative to the optimal policy.The approach is first described for a known horizon.Source: §3 · p. 3
  • Under Assumption 2.1, SWA achieves a regret bound stated in Theorem 3.1.The supplied passage does not include the bound’s expression.Source: §3 · p. 3
  • For an unknown horizon, wSWA applies SWA over successively doubled horizons and achieves the same horizon-dependent regret rate.The horizon sequence uses powers of two.Source: §3 · p. 3

4 Parametric Case

The parametric case uses a known family of rotting models plus unknown arm-specific constants, and develops separate approaches for asymptotically vanishing and non-vanishing cases. CTO-based methods detect rotting models and balance or estimate arm values; their guarantees depend on the stated model and detection assumptions.

4 Parametric Case

  • The parametric case assumes each expected reward combines an unknown constant part with a rotting part from a known model set; the rotting models are positive, non-increasing, and o(1).The known set Θ is discrete.Source: §4 · p. 4

4.1 Closest To Origin (AV)

  • CTO hypothesizes the rotting model that best fits past rewards by proximity to the origin; CTOSIM reapplies this rule at each decision point and selects an arm by argmax, breaking ties toward fewer pulls.CTOSIM's model-detection and balancing guarantee also requires the simultaneous balance and detection assumption.Source: §4.1 · pp. 4–5
  • CTOSIM achieves regret upper bounded by o(1) under Assumptions 4.1 and 4.2.The accompanying explanation says regret vanishes with probability 1−1/T, while in any case it is bounded by a decaying term.Source: §4.1 · p. 5

4.2 Differences Closest To Origin (ANV)

  • D-CTO addresses non-vanishing arm constants in two stages: detect the rotting model, then estimate and control pulls according to the constant terms.Its detection criterion cancels constant-term influence and compares differences between the two halves of reward sequences; the stated detection assumption makes models distinguishable by those differences.Source: §4.2 · p. 5, Assumption 4.3. (D-Detection ability) · p. 5

D-CTOUCB

  • D-CTOUCB first detects rotting models, then uses a UCB1-like rule to estimate arm constants and choose using estimated expected reward plus an upper-confidence term.The paper also describes D-CTOSIM-UCB, which makes a decision at each time step using the detection rule followed by the UCB choice rule.Source: D-CTOUCB · p. 6
  • With probability at least 1−δ, D-CTOUCB's regret bound has 32σ^2 ln T/(Δ_i−ε_i)^2 as its only time-dependent factor.The theorem applies under Assumptions 4.1 and 4.3, for ε_i∈(0, Δ_i) and i≠a*; the paper notes that ln T cannot be improved because stochastic MAB is a special case.Source: D-CTOUCB · p. 6

5 Simulations

Across the simulation cases, wSWA consistently and significantly outperformed the three benchmark algorithms, while CTOSIM or D-CTOUCB-SIM performed best when prior knowledge allowed their use. The simulations compare average regret and end-of-horizon outcomes across non-parametric and parametric settings.

Setups

  • All simulations used Normal rewards with σ^2=0.2 and T=30,000; the non-parametric case used K=2 arms.The non-parametric setup gives one arm a constant mean of 0.5 and another a mean of 1 for its first 7,500 pulls, then 0.4.Source: §5 · p. 6

Performance

  • Each case reports average regret over 100 trajectories, win counts, and paired t-test p-values for end-of-trajectory regrets; a win means lower final regret.The table's entries below the diagonal are win counts, and those above it are p-values.Source: §5 · p. 7

Results

  • With prior knowledge, CTOSIM or D-CTOUCB-SIM outperformed all other algorithms, including wSWA; without it, wSWA consistently and significantly outperformed the three benchmarks.The table reports algorithm win counts and p-values, while Figure 1 plots average regret for the non-parametric, parametric AV, and parametric ANV cases.Source: §5 · p. 7, Table 1 · p. 7, Figure 1 · p. 7

6 Related Work

Related work spans stationary, adversarial, hybrid, and non-stationary bandits. The paper distinguishes its rested setting, where only a chosen arm's reward distribution changes, from nearby approaches with different dynamics or assumptions.

Stochastic MAB

  • In stationary stochastic MAB, reward distributions stay fixed and the optimal policy pulls one fixed arm; common approaches include upper-confidence-bound indices and Thompson Sampling.The passage cites Gittins [1979] for optimal index policies and Thompson [1933] for Thompson Sampling.Source: §6 · p. 8

Adversarial MAB

  • Adversarial MAB allows arbitrary reward sequences and measures regret against the best fixed action in hindsight, unlike this paper's policy regret against the best action sequence.The passage cites [Auer et al., 2002b, Hazan and Kale, 2011] for adversarial regret.Source: §6 · p. 8

Hybrid models

  • Hybrid models include rewards that change arbitrarily between constant epochs or arms that expire and are replaced, while an unexpired arm's statistics remain unchanged.Garivier and Moulines [2008] and Yu and Mannor [2009] study epoch changes; Chakrabarti et al. [2009] study expiring arms.Source: §6 · p. 8

Non-Stationary MAB

  • Among non-stationary work, the paper's rested setting differs from restless models with known stochastic evolution, and from approaches with action-independent reward sequences or deterministic rewards.Komiyama and Qin [2014] study decay models in a restless setting; Besbes et al. [2014] assume action-independent expected-reward sequences and bounded support, while Heidari et al. (2016) study deterministic rewards.Source: §6 · p. 8

7 Discussion

The paper introduces Rotting Bandits, where arm rewards decay or generally do not increase with pulls, and develops algorithms for non-parametric and parametric settings. It reports theoretical guarantees and simulations, while identifying open directions for extending the analysis.

7 Discussion

  • Rotting Bandits models expected rewards that decay or generally do not increase as an arm is pulled.The authors describe this as a novel variant of the Rested Bandits framework, motivated by real-world scenarios.Source: §7 · p. 8
  • For the non-parametric case, with no prior knowledge of the decay, the paper presents an easy-to-follow algorithm with theoretical guarantees.The authors identify this as their first case tackled.Source: §7 · p. 8
  • The parametric analysis distinguishes rewards that decay to zero (AV) from those that decay to different constants (ANV).The paper reports suitable algorithms for both scenarios, with stronger guarantees than in the non-parametric case.Source: §7 · pp. 8–9
  • For AV, the algorithm guarantees expected regret bounded by a term that decays to zero with the horizon; for ANV, it gives a high-probability rate optimal for the stationary case.The paper also reports that simulations showed its algorithms outperforming non-stationary MAB benchmarks, while noting that suitable benchmarks for the novel Rotting Bandits setting were unavailable.Source: §7 · p. 9
  • Future work includes proving a regret lower bound for the non-parametric case and extending the parametric case to continuous parameterization.These are the two directions identified by the authors.Source: §7 · p. 9

B.1 Proof of Lemma 2.1

The proof establishes that the policy choosing an arm with the highest current expected reward is optimal. It does so by transforming a proposed better policy into policies with non-decreasing expected total reward.

B.1 Proof of Lemma 2.1

  • At the first deviation from πmax, the construction follows the candidate policy until that time, then applies the argmax rule before rejoining it.When multiple arms maximize expected reward, the constructed policy chooses the same action as πmax.Source: §B.1 · p. 11
  • The exchange step preserves or increases expected total reward because expected arm rewards are non-increasing with pulls.The proof invokes this assumption alongside the argmax rule.Source: §B.1 · p. 11
  • The proof concludes that πmax is optimal, contradicting the assumption that another policy earns greater expected total reward.The argument recursively constructs policies with non-decreasing expected total reward until the policy no longer deviates from πmax.Source: §B.1 · p. 11

C.1 Proof of Thm. 3.1

The proof bounds the regret of SWA by limiting how often it pulls significantly sub-optimal arms, then accounting for concentration-bound violations. It uses the order-independence of expected total reward under the rested-arm model.

C.1 Proof of Thm. 3.1

  • The expected total reward of a policy depends on how many times each arm is pulled, not on the order of those pulls.This follows because an arm's expected rewards depend on its pull count rather than the time step.Source: §C.1 · p. 11
  • SWA ensures that no arm is pulled more than M times while its expected reward is at least 2q below the current optimal arm's reward.The proof establishes this limit by induction, using the non-increasing reward assumption.Source: §C.1 · p. 12
  • The proof separately accounts for violations of the concentration condition, bounding the probability of any violation by using the per-test bound and the number of tests.If the condition is violated, total reward is bounded using the non-increasing reward assumption.Source: §C.1 · p. 13
  • The proof establishes Theorem 3.1 by bounding SWA's regret using an earlier result for πd max.The derivation cites the policy optimality lemma, a bound from Heidari et al. [2016], and the proof's preceding bound.Source: §C.1 · p. 13

C.2 Proof of Corollary 3.1.1

The proof derives the corollary by dividing the horizon into intervals and applying the known-horizon regret bound. It uses optimality of πmax to relate the interval rewards to the policy's regret.

C.2 Proof of Corollary 3.1.1

  • The proof defines regret and expected total reward for both a single policy and a policy switched after a specified time.These definitions let it express regret over the intervals used in the argument.Source: §C.2 · p. 13
  • πmax's expected reward over an interval is the sum of rewards selected from the sorted list of all arm rewards, supporting the interval comparison.The proof characterizes this as the lowest possible sum of the interval's highest elements after the preceding pulls.Source: §C.2 · p. 14
  • The proof applies the known-horizon regret bound on successive intervals, then sums their regret to obtain the corollary's bound.It uses additive regret across intervals and bounds the resulting sum using a geometric series.Source: §C.2 · p. 14

D.1 Proof of Thm. 4.1

The proof establishes that CTOSIM reaches zero regret after a finite balancing period under correct model detection, then bounds the probability of later misdetection. It also derives the regret bound for πD-CTOUCB and checks the theorem’s assumptions in an example.

D.1 Proof of Thm. 4.1

  • With correct detection, CTOSIM reaches zero regret and remains optimal thereafter; accounting for misdetection, it achieves zero regret with probability at least 1 − 1/T for T ≥ T*SIM.Feasibility is shown by bounding detection and balancing steps within the horizon.Source: §D.1 · pp. 16–18

D.2 Proof of Thm. 4.2

  • The proof shows m*diff(δ/K) is finite, then uses model-detection and pull-count bounds to obtain the stated regret result for πD-CTOUCB.The exploration phase pulls each arm m*diff(δ/K) times before the Detect step.Source: §D.2 · p. 20, Bounding number of pulls · p. 20

Bounding number of pulls

  • For bounding pulls, the analysis assumes the true rotting models are detected with probability at least 1 − δ and bounds pulls through concentration inequalities.The stated result follows by plugging those bounds into the regret upper bound.Source: Bounding number of pulls · p. 20

E Example 4.1

  • The Gaussian reward example uses a discrete parameter set with 0.01 ≤ θ ≤ 0.49 to demonstrate the stated assumptions.For these parameters, n^-θ is positive, non-increasing in n, and tends to zero.Source: E Example 4.1 · p. 21, §E.1 · p. 21

E.2 Assumption 4.2

The examples verify Assumptions 4.2 and 4.3 for the considered parameter setting by bounding the relevant expressions for sufficiently large n.

E.2 Assumption 4.2

  • For sufficiently large n, the example’s bounds establish that Assumption 4.2 holds, with bal(x) = x^4.9.The argument uses 0.01 ≤ θ ≤ 0.49 and a sufficiently large threshold.Source: §E.2 · p. 21

E.3 Assumption 4.3

  • The same large-n bounding argument establishes Assumption 4.3 for the considered parameter setting.The inequalities follow the arguments used for Assumption 4.2.Source: §E.3 · p. 22
Loading 1702.07274v4…