1
$\begingroup$

In Li et al. (2010)'s highly cited paper, they talk about LinUCB with hybrid linear models in Section 3.2.

They motivate this by saying, "In many applications including ours, it is helpful to use features that are shared by all arms, in addition to the arm-specific ones. For example, in news article recommendation, a user may prefer only articles about politics for which this provides a mechanism."

I don't quite understand what they mean by this. Is anyone willing to provide a different example? Also it would greatly help if you can clarify what Equation 6's "$\mathbf{z}$" and "$\mathbf{x}$" refer to in the context they talk about (news recommendation), or the example you give?

Equation (6) from the paper:

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

$\endgroup$
3
$\begingroup$

Let's first take a look at equation 6:

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

Some quick observations:

  • The feature vector $\mathbf{z}_{t, a}$ has time $t$ and arms $a$ as subscripts. This means that we can have different vectors $\mathbf{z}_{t, a}$ for every time step $t$ and every arm $a$.
  • The feature vector $\mathbf{x}_{t, a}$ has time steps $t$ and arms $a$ as subscripts. These are exactly the same subscripts we also saw in $\mathbf{z}_{t, a}$. So, again, this means that we can have different feature vectors $\mathbf{x}_{t, a}$ for every time step $t$ and every arm $a$.
  • The parameters or weights vector $\boldsymbol{\beta}^*$ does not have any subscripts. This is the optimal vector (the star denotes optimality) that we aim to approximate through learning. This means that we learn only a single vector $\boldsymbol{\beta}$ that is used across all timesteps and all arms (of course, since we're learning it, it does actually actually change over time in practice; not because it should inherently change over time, but because we're still learning it).
  • The optimal parameter vector $\boldsymbol{\theta}_a^*$ (which we aim to approximate as $\boldsymbol{\theta}_a$ through learning) has arms $a$ as a subscript. This means that, for every arm $a$, we'll learn a separate parameter vector $\boldsymbol{\theta}_a$.

First a couple of corrections, some things I don't think are correct / clear in the paper:

  • In the paper, as you also quoted in the question, they say "it is helpful to use features that are shared by all arms, in addition to the arm-specific ones." This is in reference to the new feature vectors $\mathbf{z}_{t, a}$ that they're introducing there. However, we've just observed above that, due to having subscripts $a$, these feature vectors are in fact arm-specific, and not shared by all arms. However, we use these feature vector to take a dot product with a learned parameter vector $\boldsymbol{\beta}$, which in turn is shared across all arms. Intuitively, this means that we're saying that these feature vectors $\mathbf{z}_{t, a}$ can have different feature values per arm, but the "importance" of every value in such a vector is the same regardless of the arm we're looking at.
  • Since we assume that feature vectors $\mathbf{z}_{t, a}$ can be relevant for predicting rewards, it should also be included in the expectation on the left-hand side of equation 6, which should therefore be changed to:

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


Example

Suppose at every time $t$, a new customer enters our shop, and we have to pick one of a set of books (arms $a$) to try selling to that customer (note; this is actually very similar to news article recommendation, or selecting which Ad to display, or any other common MAB problem).

In feature vectors $\mathbf{x}_{t, a}$, we want features that we expect to have different influences on our chances of a successful sale per book. For example:

  • Age (kids will tend to prefer certain books, adults will tend to prefer others)
  • A measure of how many other books in the same genre that particular customer has bought before
  • etc.

In feature vectors $\mathbf{z}_{t, a}$, we want features that we expect to have the same influence on our chances of a successful sale regardless of what book we're looking at (note; the feature values may still be different per arm $a$ or time step $t$, we just expect their influence or importance to be the same / similar. For example:

  • A variable that is e.g. $1$ if the customer $t$ has enough money to buy a book $a$, or $-1$ if they don't have enough money. Note that the feature value can differ per customer and per book (different customers have different amounts of money, and different books have different prices), but we expect the influence to always be the same; if they have enough money, they might buy it, otherwise, they're very unlikely to buy it.
  • Age: yes, I'm aware that I already put this feature in the other list above as well. We might want to have it in both feature vectors. We put it in the previous list because we expect there to be book-specific preference levels depending on age. However, it might also be the case that certain age groups tend to buy more books than other age groups in general, so it might be beneficial to simply have it in both feature vectors (for different expected effects).
$\endgroup$

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.