How to test if bandit algorithm is converging?

Question

I have coded up the a multi-armed bandit algorithm based on algorithm 1 in the original LinUCB algorithm paper, but I am having trouble determining if it is working properly.

My test setup is the following:

• I created some random context data matrix, with D=np.random.random( (10000,3)), where each row is a training example (user) and each column is a feature for that user / training example. Each row is $x_t$ from the algorithm.
• I then created 100 arms where each arm is represented by a Bernoulli distribution with varying $p$ (probability) values.

In fact the logic of each arm's reward distribution is the following:

if random.random() > self.p:
    return 0.0
else:
    return 1.0

• The different p-values of the arms are defined by np.random.random(100), which means I know what the best/worst arms are beforehand.

The test then follows these steps:

1. Step through each row of $D$ from $x_1$ to $x_{10000}$
2. At each $x_t$, go through every bandit arm, from $a_1$ to $a_{100}$ and estimate the payoff, $p_a$, using the formula from the paper.
3. Choose the arm with the highest estimated payoff, call this $a_t$.
4. With the recommended arm, $a_t$, sample its Bernoulli distribution using the logic above with its respective $p$-value. Call this $R_{t,a}$. At the same time, sample best arm's reward (arm with highest $p$ value), call this $R_t^*$
5. Calculate $Regret=R_t^*-R_{t,a}$ and record this at each step $t$.

Now, after running this, according to the paper, the cumulative regret over each time step should be logarithmic or $O(\sqrt{KdT} )$. But when I plot the cumulative sum of Regret over each timestep, it is simply linear. Where am I going wrong? What other methods could I use to tell if it is converging?

Note: I haven't posted all my code as I wanted to make sure the broader approach made sense and was correct before going into the nitty-gritty details.

Answer 1

All the way at the end of the right column on page 3, the LinUCB paper says:

"we can adapt the analysis from [6] to show the following: if the arm set $\mathcal{A}_t$ is fixed and contains $K$ arms, then [...], and then prove the strong regret bound of $\tilde{O}(\sqrt{KdT})$, matching the state-of-the-art result [6] for bandits satisfying Eq. (2)."

Now, that last part ("for bandits satisfying Eq. (2)") is slightly ambiguous in my opinion, it can be interpreted in two different ways:

1. That bound was the state-of-the-art for bandits satisfying Equation (2), OR
2. This particular paper also relies on Equation (2)

I didn't go through the referenced paper (reference [6]) yet to see if the actual analysis also requires Equation (2) to hold, but I suspect it does. Right above Equation (2), the LinUCB paper does say:

"[...] we assume the expected payoff of an arm $a$ is linear in its $d$-dimensional feature vector $\mathbf{x}_{t, a}$ with some unknown coefficient vector $\boldsymbol{\theta}_a^*$; namely, for all $t$,

$$\mathbf{E} \left[ r_{t, a} \vert \mathbf{x}_{t, a} \right] = \mathbf{x}^{\top}_{t, a} \boldsymbol{\theta}_a^*$$"

Generally, when a paper says "we assume" like that, that indicates that their later theoretical results rely on that assumption unless they later on specifically indicate for one of their theoretical results that it does not rely on that assumption. So, now it's time to see if that assumption actually holds in your case.

Unless I'm misunderstanding a part of your description, it looks to me like the context vectors $\mathbf{x}_t$ are actually useless in some sense; they do not in reality have any relation whatsoever to the reward distribution. This kind of means that you have a standard Multi-Armed Bandit problem (not contextual), but it's "disguised" as a Contextual MAB problem.

In your case, the rewards are completely independent from the context vectors, which means Equation 2 from the paper cannot hold; the expectation of the reward given a context vector cannot be a linear function of that context vector. The assumptions of the theoretical analysis leading to that regret bound do not hold, so the results do not hold either (at least, not necessarily; they still might by coincidence).

---

Note that, in your case, under the assumption that you're learning a separate parameter vector $\boldsymbol{\theta}_a$ per arm $a$, there is a very easy way to make the assumption of Equation (2) hold; simply add a fourth feature to every feature vector $\mathbf{x}_t$ which always has a value of $1$ (very much like an "intercept" or "bias" term that's often used in things like Linear Regression, Logistic Regression, Neural Networks, etc.). Hopefully, the algorithm should then be able to learn that the three other features are completely useless for predictions, and learn to predict a consistent estimate of the expected rewards of all the arms independent of the remaining three features.

---

The following procedure was described in the question for evaluating regret:

4. With the recommended arm, $a_t$, sample its Bernoulli distribution using the logic above with its respective $p$-value. Call this $R_{t,a}$. At the same time, sample best arm's reward (arm with highest $p$ value), call this $R_t^*$
5. Calculate $Regret=R_t^*-R_{t,a}$ and record this at each step $t$.

I was inclined to say that this was not 100% correct, but it actually does appear to be correct according to the formal definitions of regret.

I didn't originally feel like it was 100% correct, because the best arm with respect to expected reward ($p$) is not necessarily the best arm in any single given round. This evaluation method can theoretically lead to negative regret (consider the case where a suboptimal arm was played, but that suboptimal arm randomly got "lucky" and produced a better reward in one particular timestep).

Before looking up the formal definitions, I was inclined to say that a better evaluation method would be to generate the actual reward outcomes in a time step for all arms, and subtract the reward of the chosen arm from the best possible reward in that timestep to compute that timestep's regret. In comparison to your evaluation method, this approach;

• can never result in a negative regret
• is more "strict" / punishing for suboptimal strategies
• results in a regret of precisely $0$ for a "cheating" or "oracle" strategy that always knows which arm is the best and picks the best

When comparing the performance of multiple different algorithms, both variants of computing regret would always lead to the same ordering of algorithms' performance levels.