PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards

Omar Besbes, Yonatan Gur, Assaf Zeevi

arXiv:1405.3316v2cs.LGmath.OCmath.PRstat.ML

TL;DR

Non-stationary rewards add a remembering–forgetting tension to the exploration–exploitation trade-off. The paper introduces a nonparametric model and characterizes minimax regret, including a rate of order (KVT)^(1/3)T^(2/3).

  • Problem

    Non-stationary rewards add a remembering–forgetting tension to the exploration–exploitation trade-off.

    Source: §3.3 · p. 13

  • Method

    The paper introduces a nonparametric modeling paradigm for non-stationary reward environments.

    Source: §1 · p. 4

  • Results

    Minimax regret is of order (KVT)^(1/3)T^(2/3).

    Source: §1 · p. 4

  • Takeaways & Limitations

    The minimax-regret rate depends on K, V, and T.

    Source: §1 · p. 4

    Numerical results focus on β up to 0.5; for higher β, observing asymptotic regret requires a horizon significantly longer than 3 · 10^8.

    Source: §4 · p. 15

Abstract

from arXiv · show

In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of play T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation); the price paid due to this trade off is often referred to as the regret, and the main question is how small can this price be as a function of the horizon length T. This problem has been studied extensively when the reward distributions do not change over time; an assumption that supports a sharp characterization of the regret, yet is often violated in practical settings. In this paper, we focus on a MAB formulation which allows for a broad range of temporal uncertainties in the rewards, while still maintaining mathematical tractability. We fully characterize the (regret) complexity of this class of MAB problems by establishing a direct link between the extent of allowable reward "variation" and the minimal achievable regret. Our analysis draws some connections between two rather disparate strands of literature: the adversarial and the stochastic MAB frameworks.

1 Introduction

The introduction presents a tractable nonparametric model for non-stationary rewards, using a total-variation budget to characterize minimax regret against a dynamic oracle. It also highlights memory and unknown variation as challenges for policies benchmarked against this comparator.

Modeling

  • The nonparametric model bounds total variation in cumulative mean rewards by VT, supporting broad temporal evolutions and a dynamic-oracle benchmark rather than the adversarial setting’s static benchmark.The framework extends beyond models focused on a finite number of changes in mean rewards.Source: §1 · p. 4

Minimax regret characterization

  • With cumulative temporal variation bounded ex ante by VT, minimax regret against a dynamic oracle that knows the mean-reward evolution is Θ((KVT)^(1/3) T^(2/3)), and a constructed policy achieves this order uniformly over temporally varying reward sequences.Source: §1 · p. 4
  • With constant VT, regret grows as T^(2/3); when VT is of the same order as T, regret is linear and no policy can achieve sublinear regret.The minimax complexity spans intermediate scales as the variation budget grows with T.Source: §1 · pp. 4–5

Elucidating exploration-exploitation tradeoffs in the presence of non-stationary rewards

  • Non-stationarity adds a memory tradeoff: policies must forget previously acquired information at a suitable rate as reward distributions change.The proposed policy accounts for exploration and exploitation while highlighting this additional requirement.Source: §1 · p. 5

Towards adaptive policies

  • The sharp minimax policy requires a known ex ante variation bound, leaving online adaptation to unknown variation unresolved.The paper proposes an envelope policy that switches among subordinate policies built for different budget assumptions; numerical results support the plausibility of optimality, but there is no proof, and theoretical analysis is left for future work.Source: §1 · p. 5

Further contrast with related work

  • Unlike Auer et al. (2002) and Garivier and Moulines (2011), which restrict changes in the best arm to finitely many times, this analysis treats a broader, more flexible class of temporal changes.Those two works are described as the closest related papers, respectively in adversarial and stochastic settings.Source: §1 · p. 5

Introduction

  • The framework uses a dynamic oracle as its benchmark, providing a more realistic policy comparator absent from the adversarial MAB formulation.This adds a dynamic comparator to the adversarial formulation.Source: §1 · pp. 5–6
  • The variation-budget concept was advanced by Besbes et al. (2015) for a non-stationary stochastic approximation problem.Source: §1 · p. 6
  • The paper's analysis is distinct from Besbes et al. (2015), which studies continuous convex optimization.Source: §1 · p. 6

2 Problem Formulation

The section formalizes a non-stationary K-arm bandit with time-varying mean rewards and measures policy performance against a dynamic oracle that selects the highest-mean arm each round. It constrains temporal change with a cumulative variation budget and frames performance as worst-case regret over sequences within that budget.

2 Problem Formulation

  • Policies choose among K arms using past actions and observations, may randomize, and receive noisy rewards with arm-specific means.The mean-reward sequence is selected by a non-adaptive adversary, subject to the variation constraint.Source: §2 · pp. 6, 8
  • Figure 1 illustrates that equal cumulative variation can occur as continuous change or as change concentrated in the first and final thirds of the horizon.In both instances, the cumulative variation is 3; mean rewards are fixed between the two periods of change in the right-hand instance.Source: Figure 1 · p. 7
  • Regret is the gap between a policy’s expected performance and the dynamic oracle’s, which selects the highest-mean arm at each epoch.In a stationary setting, this reduces to the usual regret benchmark with a constant oracle action.Source: §2 · p. 8
  • The variation budget VT bounds cumulative temporal variation in mean-reward sequences and defines the uncertainty set over which policy regret is guaranteed.The paper defines minimax regret as the smallest worst-case regret guaranteed by an admissible policy.Source: §2 · p. 8
  • The minimax formulation captures stochastic rewards from non-stationary distributions, for which a direct characterization is described as hardly tractable.The analysis derives bounds as a function of horizon T to clarify how the variation budget affects achievable performance.Source: §2 · p. 9

3 Analysis of the Minimax Regret

The analysis characterizes minimax regret under bounded reward variation, relating variation to regret bounds and examining policies including Rexp3 and Exp3.S. It also discusses how variation affects exploration, exploitation, remembering, and forgetting, and clarifies the dynamic-oracle benchmark used.

3.1 Lower bound

  • The lower bound spans regret of order T^2/3 to linear regret as the variation budget grows, ruling out sublinear regret when variation grows linearly with T.For broader temporal variation, the stationary-regime performance is no longer achievable.Source: §3.1 · p. 9

3.2 Rate optimal policy

  • Rexp3 attains the minimax regret order R*(V_T, T) ≍ (V_T)^1/3 T^2/3, matching the lower bound in its dependence on T and V_T.Its construction restarts Exp3 in batches to balance exploration and exploitation.Source: §3.2 · p. 11

3.3 Further extensions and discussion

  • Exp3.S, modified for continuous updating, guarantees near-optimal performance in the broader non-stationary stochastic setting.The paper contrasts its smoother updating with Rexp3’s batching and abrupt restarts.Source: §3.3 · p. 12
  • When V_T = C · T^β for 0 ≤ β < 1, minimax regret is of order T^(2+β)/3.Non-stationarity adds a remembering–forgetting tension: more observations can reduce estimation variance, while older information can become less useful and bias estimates.Source: §3.3 · p. 13
  • When the variation budget grows linearly with the horizon, regret must grow linearly in T.This matches the cited Brownian-motion setting of Slivkins and Upfal (2008).Source: §3.3 · p. 13
  • Garivier and Moulines (2011) and Auer et al. (2002) study settings with finitely many reward or best-arm changes, using prior knowledge of that finiteness.Their policies achieve regret relative to the best sequence of actions; the supplied passages do not specify its order.Source: §3.3 · p. 13
  • For fixed variation budget V_T, regret is at least T^(2/3), with hard instances containing many changes in expected rewards.This makes the problem’s complexity markedly different from studies that assume a finite number of changes.Source: §3.3 · p. 13
  • Unlike Auer et al. (2002), whose benchmark allows only s + 1 actions, this paper’s dynamic oracle can switch arms in every epoch.Auer et al.’s benchmark extends the single-best-action-in-hindsight benchmark but remains more restrictive than the dynamic oracle.Source: §3.3 · p. 13

4 Numerical Results

Simulations probe adjusted Exp3.S under fixed and increasing reward variation. Estimated regret growth broadly matches the theoretical rates, while a high-variation comparison shows Exp3.S can incur linear regret.

Experiment 1: Fixed variation and sensitivity to time horizon

  • The trajectory favors the highest-expected-reward arm, with minor crossover delays, but continued suboptimal-arm exploration leaves it below the dynamic oracle.The simulated trajectory uses T = 1,500,000 epochs in two complementary non-stationary instances.Source: Figure 3 · p. 15, §4 · p. 15

Experiment 2: Fixed time horizon and sensitivity to variation

  • As variation increases, the estimated regret-growth slopes illustrate the spectrum of minimax rates, including order V_T^1/3 T^2/3.The experiment examines β values from 0 to 0.5 under sinusoidal variation.Source: §4 · pp. 15–16
  • For β values above 0.5, observing asymptotic regret requires a horizon significantly longer than the 3 · 10^8 used in these experiments.The study therefore focuses on β values up to 0.5.Source: §4 · p. 15

Experiment 1: Fixed variation and sensitivity to time horizon

  • For fixed variation, log-log regret slopes are close to 2/3, consistent with the constant-variation theorem.The two instances distribute the same V_T = 3 budget differently over time.Source: §4 · pp. 14–15, Figure 4 · p. 16

Experiment 2: Fixed time horizon and sensitivity to variation

  • Estimated regret-growth slopes span the theoretical minimax rates as variation increases, and the proposed policy's numerical regret rate closely matches theory.Table 1 contrasts estimated slopes for V_T = 3T^β with theoretical minimax rates.Source: Table 1 · p. 16, §4 · p. 16
  • At β=0.5, Exp3.S’s estimated slope was 1, implying linear regret; its order-T bound does not guarantee sub-linear regret, unlike this paper’s established order-T^5/6 upper bound.In high-variation settings, Exp3.S’s empirical performance was dominated by the policies described in this paper.Source: §4 · p. 17

5 Adapting to Unknown Variation

This section examines how policies can adapt to unknown reward variation by combining policies tuned to different variation levels, characterizing the cost of inaccurate tuning and evaluating an envelope policy numerically. The numerical analysis compares versions with two and three subordinate policies and reports sensitivity to the sinusoidal functions’ initial amplitude.

5 Adapting to Unknown Variation

  • With VT = T^α and zero actual variation, Rexp3 incurs regret of order T^((2+α)/3), versus the T^(1/2) rate possible when zero variation is known.Source: §5 · pp. 17–18
  • When tuned with VT = T^α, Rexp3 guarantees long-run average optimality if actual variation is at most T^(α+δ), for δ < (1−α)/3.The section also notes that actual variation exceeding the input budget can cause additional regret.Source: §5 · p. 18

5.1 An envelope policy

  • The envelope policy selects among subordinate policies tuned to different variation-budget guesses, switching according to realized rewards.The authors present this as a possible approach to adaptation, without proving optimality or offering strong theoretical evidence for the policy family.Source: §5 · p. 18, §5.1 · p. 18

5.2 Structure of the subordinate policies

  • The subordinate policies are adjusted Exp3.S policies, and their identical updates share reward information across policies.Source: §5.2 · p. 19

5.3 Numerical Analysis

  • The envelope policy’s regret slopes appear close to those achievable with prior knowledge across variation levels, though uncertainty may increase the multiplicative constant.The authors also suggest the approach may work when the possible variations cannot be limited in advance.Source: Figure 5 · p. 20, §5.3 · p. 21
  • 0.352 is the log-log intercept for the fixed-variation case under the envelope policy, versus -0.358 when that variation is known a priori.Source: §5.3 · p. 21
  • The analysis considered an envelope with two subordinate policies guessing no variation and increasing variation, with three log-log plots shown for the cases.Source: §5.3 · p. 21
  • Despite sensitivity to the sinusoidal functions’ initial amplitude, the two-policy envelope achieved comparable average performance to the three-policy version, which included a well-specified policy.The comparison appears in the numerical analysis of three cases.Source: §5.3 · p. 21

A Proofs of main results

The proofs establish a variation-dependent regret lower bound and analyze upper bounds for Rexp3 and Exp3.S using batches of decisions. For unknown horizon T, they use exponentially increasing epochs to bound regret within each epoch and across the full horizon.

Proof of Theorem 1

  • Any policy incurs regret of order (KVT)^(1/3)T^(2/3) on a restricted class with one good arm per epoch and rewards fixed within each batch.The lower-bound proof adapts a worst-case strategy to this class of reward sequences.Source: A Proofs of main results · p. 21

Proof of Theorem 2

Proof of Theorem 3

  • For the non-stationary stochastic setting, tuned Exp3.S achieves near-optimal performance by batching and bounding regret against the sequence of batch-best actions.The proof then selects tuning parameters to minimize overall regret.Source: A Proofs of main results · p. 25

A Proofs of main results

  • When T is unknown, the proof uses Exp3.S over exponentially increasing epochs Tℓ = 2^ℓ, ℓ = 0, 1, 2, …, following a method similar to Corollary 8.4 of Auer et al. (2002).Source: A Proofs of main results · pp. 27–28
  • Regret incurred during an epoch of length Tℓ is at most C (KVTℓ log(KTℓ))^(1/3) · Tℓ^(2/3).Source: A Proofs of main results · p. 28
  • Rπ(V, T) ≤ C̃ (log(KT))^(1/3) (KVT)^(1/3) T^(2/3) for an absolute constant C̃.This is the regret bound over the full horizon.Source: A Proofs of main results · p. 28
Loading 1405.3316v2…