Cumulative Regret

cumulative-regret

Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit — Cao et al. (2018) (arXiv:1802.03692, 2018)

What this evaluates

Evaluates piecewise-stationary multi-armed bandit algorithms by measuring the expected cumulative regret over a sequence of time steps. It probes how well an algorithm adapts to changing arm reward distributions (change-points) while balancing exploration and exploitation.

Datasets

• Yahoo! Front Page Today Module User Click Log Dataset — total ?; splits: test (432000); repo https://webscope.sandbox.yahoo.com

Metrics

• cumulative regret (primary) — range: other
  • Expected cumulative regret is defined as E[sum_{t=1}^T (mu^t - mu{A_t})], where mu^t is the mean reward of the optimal arm at time t, mu{A_t} is the mean reward of the selected arm, and the expectation is averaged over 100 independent Monte Carlo trials.

Input / output format

Input: At each time step t, the algorithm receives the current arm selection A_t and observes a binary reward (click/no-click) drawn from a piecewise-stationary Bernoulli distribution. The environment provides a sequence of T time steps with K arms.

Output: A single arm index A_t in {1, ..., K} selected at each time step t.

Scoring recipe

def compute_cumulative_regret(rewards, actions, T):
    regret = 0.0
    for t in range(T):
        best_arm_reward = max(rewards[t])
        chosen_arm_reward = rewards[t][actions[t]]
        regret += best_arm_reward - chosen_arm_reward
    return regret / 100  # Average over 100 Monte Carlo trials

Common pitfalls

• The Yahoo dataset experiment uses small-magnitude change-points (<0.1) that violate the paper's theoretical assumption (requires ≥0.64), making the comparison theoretically inconsistent but practically relevant.
• Regret scaling experiments use synthetic data with fixed change-point intervals and specific parameter bounds, which may not reflect real-world non-stationarity patterns.
• The metric is averaged over 100 Monte Carlo trials, but standard deviations or confidence intervals are not explicitly reported in the figures.

Evidence (verbatim from paper)

The expected cumulative regret is computed by taking the average of the regrets for 100 independent Monte Carlo trials, as shown in Figure 4. We compare the expected cumulative regret of different algorithms using the benchmark dataset publicly published by Yahoo! ... This dataset provides a binary value for each arrival to represent whether the user clicks the specified article ... We use one arm to represent one article and assume a Bernoulli reward (one if the user clicks the article and zero otherwise).

Citation

@misc{cao2018nearly,
  title={Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit},
  author={Cao et al. (2018)},
  year={2018},
  note={arXiv:1802.03692}
}

• arXiv: 1802.03692