Discounted UCB in a Changing Environment

Overview

When reward distributions change, a long history of observations can slow adaptation. This study compares UCB with an exponentially weighted variant in a two-arm environment whose best arm switches halfway through a run.

The archived code discounts only the selected arm. This differs from standard elapsed-time discounting in discounted UCB. The distinction is central to interpreting the results below.

What time-based discounting means

Let $A_s$ denote the selected arm at step $s$, $r_s$ its observed reward, and $0<\gamma\leq1$ the discount factor. After step $t$, define

$$N_t(i)=\sum_{s=1}^{t}\gamma^{t-s}\mathbf1\{A_s=i\}, \qquad S_t(i)=\sum_{s=1}^{t}\gamma^{t-s}r_s\mathbf1\{A_s=i\}.$$

For $N_t(i)>0$, the discounted mean is $\widehat\mu_t(i)=S_t(i)/N_t(i)$. An arm's older observations lose weight with every elapsed round, whether or not that arm is selected.

The following dependency-free example updates these statistics. It is not a complete policy: action selection, initialization, and the confidence bonus must also be specified.

def update_discounted_statistics(counts, sums, arm, reward, gamma):
    if not 0 < gamma <= 1:
        raise ValueError("gamma must be in (0, 1]")
    if len(counts) != len(sums) or not 0 <= arm < len(counts):
        raise ValueError("counts, sums, and arm must describe the same arm set")
    next_counts = [gamma * count for count in counts]
    next_sums = [gamma * total for total in sums]
    next_counts[arm] += 1
    next_sums[arm] += reward
    return next_counts, next_sums

Discounting both a sum and its count leaves an unselected arm's mean unchanged, but reduces its effective evidence. A discounted confidence rule can then encourage revisiting it.

For an arm selected every round, its count approaches $1/(1-\gamma)$ when $\gamma<1$. This is an approximate memory scale, not a guarantee of the best setting. “Close to one” is not mathematically equivalent to one.

What the archived code actually does

In lib/DiscountedUCBBandit.py, the selected arm receives

$$N_i\leftarrow\gamma N_i+1,\qquad S_i\leftarrow\gamma S_i+r.$$

All other arms retain their previous statistics. Thus an observation is discounted according to later selections of the same arm, not according to elapsed global time. The code's confidence bonus uses the undiscounted update counter:

$$\widehat\mu_i+\sqrt{\frac{2\alpha\log t}{N_i}}.$$

For example, after selecting arm 0 once and then arm 1 twice, the time-discounted count of arm 0 is $\gamma^2$. The archived implementation keeps that count at 1.

The experiment should therefore be read as a comparison with this selected-arm-discount variant. The illustrative update above explains the standard time-based statistics; it does not retroactively change the archived results or update the external repository.

Experiment setup

The linked simulation configures:

The comparator chooses the best arm at each step, including after the switch. Regret uses expected reward gaps: the simulator adds the same noise to the selected and optimal rewards, so the noise cancels in their difference. In this binary-mean environment, each suboptimal action contributes one unit.

The script logs at zero-based iterations 0, 100, …, 900, then prints the last logged value. That value covers 901 actions, not all 1,000. The source needs an explicit final checkpoint before its printed output can be called full-horizon regret.

Recorded results

The five-trial table is preserved from the original report. The mean row is the arithmetic mean of the displayed values. Seeds and per-run logs were not preserved alongside the table, so these values have not been re-established as full-horizon totals.

Within these recorded values, all three discounted variants have lower means than UCB. The $\gamma=0.5$ setting has the lowest mean, but five trials without matched seeds or uncertainty estimates do not establish a broadly optimal discount factor. These runs also do not measure the standard time-discounted algorithm.

UCB: five recorded trials

Discounted variant, gamma = 0.1: five recorded trials

Discounted variant, gamma = 0.5: five recorded trials

Discounted variant, gamma = 0.9: five recorded trials

Reproduction notes

Use the repository's main branch and SimulationDiscountedUCB.py, which preserves the archived experiment's simulation script unchanged. The algorithm dictionary selects UCB or DiscountedUCBBandit and sets $\alpha$ and $\gamma$.

A revised experiment should distinguish the archived variant from a time-discounted implementation, append the final-horizon checkpoint, and use matched seeds across methods. Testing multiple change points, reward gaps, and stationary periods would show whether faster forgetting helps consistently.

The curves above remain the original archive. No simulations were rerun for this content revision.

Takeaways

• Forgetting by elapsed time and forgetting by arm selections are different algorithms.
• Smaller discount factors can improve responsiveness while increasing estimation noise.
• A performance table must identify the implemented policy, comparator, and recorded horizon.
• These archived trials motivate a controlled rerun; they do not validate a universal ranking.

Sources

• Original discounted-bandit experiment
• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems