5
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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:

  1. 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^*$
  2. 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.

$\endgroup$
10
  • $\begingroup$ Thanks so much. This makes sense and explains why even if though the estimated $\theta_a$ are not converging, the algorithm still manages to find the best arms. It is acting like a traditional multi-armed bandit problem, but without any use of the contexts as you described. I will try adding a bias as you mention to see if the code is correct. Is my method of calculating regret correct? $\endgroup$
    – guy
    Jul 29, 2018 at 18:29
  • 1
    $\begingroup$ @guy That's an... interesting question which I kinda mistakenly glossed over initially. Edited my thoughts on that into my answer, but it's not quite a conclusive answer. $\endgroup$ Jul 29, 2018 at 18:53
  • 1
    $\begingroup$ That's just what I expect though, I might be wrong. The best thing to do is to try to evaluate what happens in such cases empirically. $\endgroup$ Jul 30, 2018 at 16:52
  • 1
    $\begingroup$ @guy Hmm if I look at papers such as this one, it looks like cumulative regret plots that at least "look" linear aren't that uncommon in practice. It may simply take more time to learn adequately for a problem with 100 arms. You could try lowering to e.g. 10 arms, see what happens. It looks like proper tuning of the $\alpha$ parameter can also have a significant influence. $\endgroup$ Jul 31, 2018 at 8:16
  • 2
    $\begingroup$ @guy great, thanks for the update! Enjoyed this discourse, Dennis and guy, thanks! $\endgroup$
    – Matthew
    Dec 13, 2018 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.