Answers.Body: <blockquote>
  <p>Conceptually, in general, how is the context being handled in CB, compared to states in RL?</p>
  </blockquote>
  <p>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:</p>
  <ul>
  <li><p>If the agent is be optimised for immediate reward only (discount fatcor <span class="math-container">$\gamma=0$</span>), 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).</p>
  </li>
  <li><p>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.</p>
  </li>
  <li><p>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.</p>
  </li>
  </ul>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T16:54:29.240Z
Answers.LastActivityDate: 2021-02-11T17:01:08.137Z
Answers.LastEditDate: 2021-02-11T17:01:08.137Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>The notion of a <em>state</em> in reinforcement learning is (more or less) the same as the notion of a <em>context</em> in contextual bandits. The main difference is that, in reinforcement learning, an action <span class="math-container">$a_t$</span> in state <span class="math-container">$s_t$</span> not only affects the reward <span class="math-container">$r_r$</span> that the agent will get but it will also affect the next state <span class="math-container">$s_{t+1}$</span> the agent will end up in, while, in contextual bandits (aka associative search problems), an action <span class="math-container">$a_t$</span> in the state <span class="math-container">$s_t$</span> only affects the reward <span class="math-container">$r_r$</span> 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 <a href="https://netflixtechblog.com/artwork-personalization-c589f074ad76" rel="noreferrer"><em>recommender system</em></a>.</p>
  <p>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.</p>
  <p>So, as Sutton and Barto put it (<a href="http://incompleteideas.net/book/RLbook2020.pdf#page=63" rel="noreferrer">2nd edition, section 2.9, page 41</a>), 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.</p>
  <p>Another important characteristic of many RL algorithms, such as Q-learning, is that they assume that the state is <a href="https://ai.stackexchange.com/q/16667/2444">Markov</a>, 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.</p>
  <p>Regarding the use of neural networks to approximate <span class="math-container">$q(s, a)$</span> or a policy in CBs, in principle, this is possible. However, given that the optimal action in a state <span class="math-container">$s$</span> is independent of the optimal action in another state <span class="math-container">$s'$</span>, 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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T17:16:33.483Z
Answers.Text: 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.
Answers.UserDisplayName: Maxim Volgin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T17:22:12.963Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T17:31:16.883Z
Answers.Text: @MaximVolgin See [page 238 of this book (section **19.2 Stochastic Linear Bandits**)](https://tor-lattimore.com/downloads/book/book.pdf#page=247), which mentions the use of a neural network as a _feature map_ in the context of bandits. [Here](http://proceedings.mlr.press/v119/zhou20a/zhou20a.pdf) 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T18:11:38.093Z
Answers.Text: 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!
Answers.UserDisplayName: Maxim Volgin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T18:17:21.343Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T16:51:59.120Z
Answers.LastActivityDate: 2021-02-11T16:59:01.390Z
Answers.LastEditDate: 2021-02-11T16:59:01.390Z
Answers.UserDisplayName: nbro
Body: <p>Conceptually, in general, how is the <em>context</em> being handled in contextual bandits (CB), compared to <em>states</em> in reinforcement learning (RL)?</p>
  <p>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?</p>
  <p>In general, what is the relation between the <em>context</em> in CB and the <em>state</em> in RL?</p>
  
Tags: <reinforcement-learning><terminology><function-approximation><state-spaces><contextual-bandits>
Title: What is the relation between the context in contextual bandits and the state in reinforcement learning?
UserDisplayName: Maxim Volgin
ThreadText: # What is the relation between the context in contextual bandits and the state in reinforcement learning?
  
  (Asked by: username_0 on 2021-02-11)
  
  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?
  
  **Tags:** reinforcement-learning, terminology, function-approximation, state-spaces, contextual-bandits
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-02-11. Score: 6 | Accepted answer
  
  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*](https://netflixtechblog.com/artwork-personalization-c589f074ad76).
  
  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](http://incompleteideas.net/book/RLbook2020.pdf#page=63)), 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](https://ai.stackexchange.com/q/16667/2444), 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).
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_2**: @username_0 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.  
  > **username_2**: @username_0 See [page 238 of this book (section **19.2 Stochastic Linear Bandits**)](https://tor-lattimore.com/downloads/book/book.pdf#page=247), which mentions the use of a neural network as a _feature map_ in the context of bandits. [Here](http://proceedings.mlr.press/v119/zhou20a/zhou20a.pdf) 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.  
  > **username_0**: 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!  
  > **username_2**: @username_0 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.  
  
  ---
  
  ### Answer by username_1 on 2021-02-11. Score: 3
  
  > 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.
  
  
  ---
  
  