Equivalence of Contextual Bandit formulations

Question

I find two different type of Contextual Bandit problem formulations in the literature:

Definition 1: (https://hunch.net/~jl/projects/interactive/sidebandits/bandit.pdf) In a contextual bandits problem, there is a distribution $P$ over $(x,r_1,...,r_k)$, where x is context, $a \in \{1,...,k\}$ is one of the k arms to be pulled, and $r_a \in [0, 1]$ is the reward for arm $a$. The problem is a repeated game: on each round, a sample $(x, r_1, ..., r_k)$ is drawn from $P$, the context $x$ is announced, and then for precisely one arm a chosen by the player, its reward $r_a$ is revealed.

Definition 2: (http://rob.schapire.net/papers/www10.pdf) The algorithm observes the current user $u_t$ and a set $A_t$ of arms or actions together with their feature vectors $x_{t,a}$ for $a \in A_t$. The vector $x_{t,a}$ summarizes information of both the user ut and arm $a$, and will be referred to as the context. Based on observed payoffs in previous trials, A chooses an arm $a_t ∈ A_t$, and receives payoff $r_t,a_t$ whose expectation depends on both the user $u_t$ and the arm $a_t$.

The fact that when stating definition number 2, the authors of http://rob.schapire.net/papers/www10.pdf cite the paper from the first definition is very confusing to me. In particular, they say "Following previous work [18], we call it a contextual bandit.1".

In particular, in Definition 1 assumes that only one context is revealed to the learner. In the second formulation, you observe "contexts" or better features for all the arms. I was thus wondering if there is any equivalence between the two formulations or a way to relate them.

All type of suggestion will be very appreciated. Thanks a lot for your help.

Answer 1

Both formulations are equivalent and compatible with standard models of contextual multi-armed bandits, where you assume that you have information available about the environment that does not depend directly of your arm choices. This context, however, can be informative and thus predictive of what rewards / regret you may face based on what arm you pull.

Examples

Let's say every morning you need to decide whether or not to bring an umbrella to work. Say your goal is to avoid getting wet while minimizing how long it takes you to get ready to leave the house over time (you could model this as a e.g. weighted combination of two objectives).

Let's consider the first model. The weather forecast (context) can help you decide whether or not you should carry an umbrella with you, but it's safe to assume that your choice (the arm you pull) of carrying an umbrella or not won't change the weather forecast over time.

Now let's consider the second model. You could carry with you an umbrella or a raincoat. Context here could include information about the arms themselves (e.g. where each of these items are in your house on that day), but again, your choice wouldn't change the weather forecast.

Relationship between those definitions

When the 2nd definition that you quote says "A context vector $x_{t,a}$ summarizes information of both the user $u_t$ and arm $a$" that's simply stating that context can be represented (understood) as a vector with per-arm features. This does not require you to assume that these features are only informative about a particular arm, or how the agent is supposed to leverage them, so the definition is equivalent to the 1st one. The difference between them is a matter of representation and does not change the problem at hand.

Note that vectorial and scalar representation (encodings) of information are equivalent here. The agent can still be assumed to see the same information at the same time, use this information however it wants, and it still needs to decide which arm to pull. For example, for all you know, all features but one could be zero always, and the problem still allows you to use the non-zero feature left to choose which arm to pull. As stated, the agent can choose to re-represent, process and encode the information provided however it sees fit.

Context and State

If you assume instead that your actions can influence some information that you have about the environment or your arms, and you want to leverage this information to optimize the problem, it's more common to call that information state instead of just context.

In the above example (e.g. 2nd model), carrying an umbrella to work may mean you could leave it in the car that night accidentally, so the following day your context would be impacted by this choice. Another example here would be a description of the screen that you see when playing a video game. This description would depend on your joystick actions (arm choices) over time.

In this case you may end up with more general Markov decision processes for modeling the problem, and e.g. reinforcement learning to learn to optimize your objective.