5
$\begingroup$

Conceptually, in general, how is the context being handled in contextual bandits (CB), compared to states in reinforcement learning (RL)?

Specifically, in RL, we can use a function approximator (e.g. a neural network) to generalize to other states. Would that also be possible or desirable in the CB setting?

In general, what is the relation between the context in CB and the state in RL?

$\endgroup$
0
3
$\begingroup$

The notion of a state in reinforcement learning is (more or less) the same as the notion of a context in contextual bandits. The main difference is that, in reinforcement learning, an action $a_t$ in state $s_t$ not only affects the reward $r_r$ that the agent will get but it will also affect the next state $s_{t+1}$ the agent will end up in, while, in contextual bandits (aka associative search problems), an action $a_t$ in the state $s_t$ only affects the reward $r_r$ that you will get, but it doesn't affect the next state the agent will end up in. The typical problem that can be formulated as a contextual bandit problem is a recommender system.

In CBs, like in RL, the agent also needs to learn a policy, i.e. a function from states to actions, but actions that you take in a certain state are independent of the actions you take in other states.

So, as Sutton and Barto put it (2nd edition, section 2.9, page 41), contextual bandits are an intermediate problem between (context-free) bandits (where there is only one state or, equivalently, no state at all) and the full reinforcement learning problem.

Another important characteristic of many RL algorithms, such as Q-learning, is that they assume that the state is Markov, i.e. it contains all necessary info to take the optimal action, but, of course, RL is not just applicable to fully observable MDPs. In fact, even Q-learning has been applied to POMDPs, with some approximations and tricks.

Regarding the use of neural networks to approximate $q(s, a)$ or a policy in CBs, in principle, this is possible. However, given that the optimal action in a state $s$ is independent of the optimal action in another state $s'$, this is probably not useful, but I cannot guarantee you that this has not been successfully done, because I've not yet read the relevant literature (maybe someone else will provide another answer to address this aspect).

$\endgroup$
7
  • $\begingroup$ thanks! regarding the last paragraph, perhaps you do know whether this approximation task can be decoupled from the rest of CB or is it an integral part of the algorithm, and in the latter case what algorithms are those? the only CB algorithms i encountered this far are linear UCB and Thompson sampling CB. $\endgroup$ – Maxim Volgin Feb 11 at 17:16
  • $\begingroup$ @MaximVolgin To be honest, I don't know. I suspect that you could do both, but maybe you will need to have a separate neural network for each state, but that doesn't look like a good approach. Like you, I'm only familiar with the typical bandit algorithms, so I can't say much about function approximation in CBs. I am also curious to see what people have been trying. Later, maybe, I will search for a few relevant papers and maybe I will update this answer to address your questions. $\endgroup$ – nbro Feb 11 at 17:22
  • 1
    $\begingroup$ @MaximVolgin See page 238 of this book (section 19.2 Stochastic Linear Bandits), which mentions the use of a neural network as a feature map in the context of bandits. Here is another potentially relevant paper, but I'm still not sure whether the neural networks here are used for the same typical purpose as in RL, as suspect that this is not the case, from what I've read there. As I said, I will update my answer later with some more relevant info. $\endgroup$ – nbro Feb 11 at 17:31
  • 1
    $\begingroup$ the first link is about linear UCB i mentioned before, but the other one (about NeuralUCB) is potentially what i need, or at least the article most probably will give me some insights. thanks! $\endgroup$ – Maxim Volgin Feb 11 at 18:11
  • $\begingroup$ @MaximVolgin Once you have read that paper (or, in general, you know more about the application of function approximation to CBs), feel free to write a formal answer below that answers your other question. $\endgroup$ – nbro Feb 11 at 18:17
3
$\begingroup$

Conceptually, in general, how is the context being handled in CB, compared to states in RL?

In terms of its place in the description of Contextual Bandits and Reinforcement Learning, context in CB is an exact analog for state in RL. The framework for RL is a strict generalisation of CB, and can be made similar or the same in a few separate ways:

  • If the agent is be optimised for immediate reward only (discount fatcor $\gamma=0$), then optimal action choice depends only on current state without considering consequences. However, the environment may not behave much like a contextual bandit over multiple time steps, so it would be hard to think in terms of the kind of optimisations that apply for CB (such as minimising regret).

  • If state progression in RL is unrelated to the action chosen, then optimal action choices depend only on the current state. There still might be some benefit from understanding the expected state progression in order to predict future rewards, and ability to learn about different states may be limited by the progression, so this in not full equivalence, but it is very close.

  • If state progression in RL is unrelated to any previous history (of states, actions, rewards), and state is drawn from the same population at any time step, then the full MDP description is not necessary, each time step is expected to be like the last. A contextual bandit model could well be more appropriate.

Another thing to consider is what your objectives are for studying the environment or applying an agent within it. Bandit solvers are usually applied to environments where the agent is expected to learn strictly online, and the goal of the developer is to write a learner that uses a minimal amount of information to decide on optimal or near optimal choices. One common metric for this is to minimise regret, or the expected difference in reward between the agent's action choices and the ideal choice summed over time.

If you have offline data to work from, then predictions for an optimal agent in a CB enviroment devolve to supervised learning of a regression task. There is no simple equivalent for this in RL, because actions have consequences that create links between states. As a result, offline RL methods are very similar to online RL ones - the state, action, reward data is processed much the same way.

$\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.