1
$\begingroup$

I am using the UCB1 algorithm to solve the multi-armed bandit problem and I would like to adapt it to handle some context vector that would influence the UCB algorithm that makes recommendations. Is there a simple way to do this?

$\endgroup$
2
  • 1
    $\begingroup$ Try having a look at LinUCB: rob.schapire.net/papers/www10.pdf $\endgroup$ Jul 12 '18 at 9:53
  • $\begingroup$ @DennisSoemers I have looked at that one but I don't know how to set it up so to speak. The math obfuscates things a bit for me. $\endgroup$
    – guy
    Jul 12 '18 at 12:43
1
$\begingroup$

The algorithm that fits that description most closely would be LinUCB, as described in Algorithm 1 of this paper.

Basically, the algorithm as described there assumes that in every round $t$, for every arm $a$, you are presented with a feature vector $\mathbf{x}_{t, a}$. For every arm $a$, it tries to learn a vector of parameters $\hat{\boldsymbol{\theta}}_a$, such that the dot product $\hat{\boldsymbol{\theta}}_a^{\top} \mathbf{x}_{t, a}$ between those two vectors estimates the reward that you expect to get from playing arm $a$ at time $t$.

That expression $\hat{\boldsymbol{\theta}}_a^{\top} \mathbf{x}_{t, a}$ is comparable to the term for the average reward of an arm in the non-contextual UCB1 algorithm (the "exploitation" term). In the paper's pseudocode, you see this expression appearing in line 9, which is basically computing the "Upper Confidence Bounds" in the contextual/linear setting.

The other expression in that line is $\alpha \sqrt{\mathbf{x}_{t, a}^{\top} \mathbf{A}_a^{-1} \mathbf{x}_{t, a}}$. This expression can intuitively be understood as the part that computes the gap between the mean/expected/predicted reward, and the Upper Confidence Bound (the "exploration term"). This is the part that should make sure that you will occasionally play an arm that does not have the highest expected reward, just for the sake of exploration. The $\alpha$ parameter is an exploration parameter (high value means lots of exploration, low values means primarily exploitation). In the non-contextual, standard version of UCB1, a similar parameter is often denoted by $C$ or simply assumed to have a constant value of $\sqrt{2}$.

The parameters $\hat{\boldsymbol{\theta}}_a$ are basically computed using an incremental variant of Ridge Regression (a variant of Linear Regression). An incremental variant is used because, in MAB problems, you generally want to learn after every time step rather than collecting a whole bunch of data and then learning at once.

Note that the algorithm involves dot products, matrix multiplications and matrix inverses. If you want to implement it, you'll likely want to make sure that you have access to a good library for linear algebra (e.g. numpy in the case of python).

For a different explanation and perhaps slightly more clear pseudocode, it looks like this could be a good blog post (didn't extensively read it though, just found it through google).


Note that there are also settings where you only have a single feature vector $\mathbf{x}_t$ per time step $t$, rather than one feature vector per arm per time step. In such a case, the same algorithm can be used, you'll just want to make sure that you then also only learn a single vector of parameters $\hat{\boldsymbol{\theta}}$, rather than one per arm.

$\endgroup$
15
  • 1
    $\begingroup$ @guy You don't need to set up that matrix explicitly, right? It doesn't appear anywhere in the algorithm. It's just described for "mathematical understanding" of what's actually happening in the algorithm. Either way, yeah, every row would be a "user" (or "time step" or "round" in a MAB problem). Every column would correspond to one feature (so there could be a "gender" column, an "age" column, a "how often has this user previously clicked ads about cats" column, anything you can think of really. $\endgroup$ Jul 15 '18 at 9:07
  • 1
    $\begingroup$ @guy If users interact more than once, they occupy more rows than one (likely with at least partially different features too if you include features describing a user's recent average behaviour for example). So yeah, saying users = rows may not be entirely correct. Would be better to say that every row is an "interaction" with the system, or just a "time step" or "decision point" or "round" $\endgroup$ Jul 15 '18 at 16:32
  • 1
    $\begingroup$ @guy No, every feature vector $\mathbf{x}_{t, a}$ should have identical dimensionality $d$. If in practice you have a case where some features only exist for some users and not for others for example, you can simply set the corresponding entries to $0$. As for your question about lines 12 and 13, that's correct. As in the traditional MAB setting, you only get feedback for the arm you decide to play, so that's the only arm for which you can update anything. $\endgroup$ Jul 18 '18 at 8:32
  • 1
    $\begingroup$ @guy Sure. If $t$ denotes the user, and $a$ the item to be recommended, different vectors $\mathbf{x}_{t,a}$ with different $a$ but the same $t$ would then partially have the same feature values; user-based feature values would all be the same across the vectors (since it's for the same user $t$), but item-based values would be different. Once you move on to the next time step (next $t$, next user), the user-based ones would also likely change $\endgroup$ Jul 20 '18 at 8:03
  • 1
    $\begingroup$ @guy That's correct. $\endgroup$ Jul 21 '18 at 8:14

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.