Answers.Body: <p>You don't need to have a reward on every single timestep, reward at the end is enough. Reinforcement learning can deal with temporal credit assignment problem, all algorithms are designed to work with it. Its enough to define a reward at the end where you, for example, give a reward of 1 if sentence is satisfactory or -1 if it isn't. Regular tabular Q-learning would easily solve the toy problem that you gave as an example.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-21T07:28:14.840Z
Answers.Text: I think this answer would be more complete, if rather than just asserting it will work, give an example answer to OP's question "But how do I update the value for the first action (choosing out of I and Trees in my example)?"
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-20T22:49:12.213Z
Answers.LastActivityDate: 2019-03-20T22:49:12.213Z
Answers.UserDisplayName: Brale
Answers.Body: <p>You are describing a straightforward Markov Decision Process that could be solved by almost any Reinforcement Learning algorithm.</p>
  
  <blockquote>
    <p>I have read a lot about RL algorithms, that update the action-value function at each step with the currently gained reward. The requirement here is, that the reward is obtained after each step.</p>
  </blockquote>
  
  <p>This is true. However, the reward value can be zero, and it is quite common to have most states and actions result in zero reward with only some specific ones returning a non-zero value that makes a difference to the goals of the agent.</p>
  
  <p>When this is more extreme - e.g. only one non-zero reward per thousand steps - this is referred to as "sparse rewards" and can be a problem to handle well. Your three steps then reward situation is nowhere near this, and not an issue at all.</p>
  
  <blockquote>
    <p>I thought that using value iteration would be an reasonable approach to test. My problem here is that I don't know how to assign the discounted reward for the chosen operations.</p>
  </blockquote>
  
  <p>Value iteration should be fine for your test problem, providing the number of choices for words is not too high.</p>
  
  <p>The way you assign discounted rewards is to use the Bellman equation as an update:</p>
  
  <p><span class="math-container">$$v(s) \leftarrow \text{max}_{a}[\sum_{s',r} p(s',r|s,a)(r + \gamma v(s'))]$$</span></p>
  
  <p>For a deterministic environment you can simplify the sum, as <span class="math-container">$p(s',r|s, a)$</span> will be 1 for a specific combination of <span class="math-container">$s', r$</span></p>
  
  <p>It doesn't matter that <span class="math-container">$r = 0$</span> for the first two steps. The Bellman equation links time steps, by connecting <span class="math-container">$v(s)$</span> and <span class="math-container">$v(s')$</span>. So, over many repetitions of value iteration's main loop, the episode end rewards get copied - with the discount applied - to their predecessor states. Very quickly in your case you will end up with values for the start states.</p>
  
  <blockquote>
    <p>For example after the last choice I get a reward of 0.9. But how do I update the value for the first action (choosing out of I and Trees in my example)?</p>
  </blockquote>
  
  <p>You don't do it directly in a single step. What happens is repeating the value iteration loop copies the best values to their predecessor states, one possible time step at a time. </p>
  
  <p>On the first loop through all states, you will run an update something like:</p>
  
  <p><span class="math-container">$$v(\text{'I'}) \leftarrow 0 + \gamma v(\text{'I am'})$$</span></p>
  
  <p>and <span class="math-container">$v(\text{'I am'}) = 0$</span> initially, so it will learn nothing useful in this first loop. However, it will also learn in the same loop:</p>
  
  <p><span class="math-container">$$v(\text{'I am'}) \leftarrow 0 + \gamma v(\text{'I am nice'})$$</span> </p>
  
  <p>So assuming <span class="math-container">$\gamma = 0.9$</span> and <span class="math-container">$v(\text{'I am nice'}) = 0.9$</span>, and that "I am high" scores less than 0.9, then it will set <span class="math-container">$v(\text{'I am'}) = 0.81$</span>. </p>
  
  <p>On the next loop through states in value iteration, it will then set <span class="math-container">$v(\text{'I'}) = 0.727$</span> (assuming "I am" beats "I are" for maximum value)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-14T10:28:42.963Z
Answers.Text: But what if the value depends on the choices, that have been made? For exampe the value of ”am” is depending on the value of the other words. But imagine I take random actions and sample a bad set of actions so that ”am” is always chosen. Then ”am” might look like the best option, not being one. And even if i then generate samples where I choose the other action the value could already be biased, or am I wrong?
Answers.UserDisplayName: Jan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-14T11:07:05.260Z
Answers.Text: @Jan: The value depending on other choices is not a problem in general, provided your state representation captures the differences (it does in this example). In value iteration, which you ask about, and which this answer uses, there is no sampling - just processing of all states and actions - so your missing sample cannot happen. However, in other solvers yes it is possible to at some stages have bad estimates because in order to learn accurate values, RL needs to sample enough variation. In tabular solvers that usually means sampling *all* variations enough times to make errors low.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-14T11:34:45.663Z
Answers.Text: But this implies, that this approach is not suitable for bigger problems, where I do not have time to sample all variations (maybe even once). Which type of Agent would be suitable in that case?
Answers.UserDisplayName: Jan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-14T11:38:00.020Z
Answers.Text: And another question: If I have to sample all variations enough times, is it not better to sample all possible variations (grid search like) and directly select the best?
Answers.UserDisplayName: Jan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-14T12:19:30.987Z
Answers.Text: @Jan: That is correct, value iteration does not scale to large problems. This is too many extra questions though, and they are different to the main question - please ask a new question on the site if you want to know more.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-21T08:04:15.573Z
Answers.LastActivityDate: 2019-03-21T08:11:38.287Z
Answers.LastEditDate: 2019-03-21T08:11:38.287Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have read a lot about RL algorithms, that update the action-value function at each step with the currently gained reward. The requirement here is, that the reward is obtained after each step.</p>
  
  <p>I have a case, where I have three steps, that have to be passed in a specific order. At each step the agent has to make a choice between a range of actions. The actions are specific for each step.</p>
  
  <p>To give an example for my problem:
  I want the algorithm to render a sentence of three words. For the first word the agent may choose a word out of <code>['I', 'Trees']</code>, the second word might be <code>['am', 'are']</code> and the last word could be chosen from <code>['nice', 'high']</code>. After the agent has made its choices, the reward is obtained once for the whole sentence.</p>
  
  <p><em>Does anyone know which algorithms to use in this kind of problem?</em></p>
  
  <hr>
  
  <p>To give a bit more detail on what I already tried:</p>
  
  <p>I thought that using value iteration would be an reasonable approach to test. My problem here is that I don't know how to assign the discounted reward for the chosen operations.</p>
  
  <p>For example after the last choice I get a reward of 0.9. But how do I update the value for the first action (choosing out of I and Trees in my example)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-10T15:29:02.847Z
Comments.Text: Why do you specifically want to use RL. These type of tasks are done by RNN and LSTM.
Comments.UserDisplayName: basujindal
Tags: <reinforcement-learning><rewards>
Title: Reinforcement Learning with long term rewards and fixed states and actions
UserDisplayName: Jan
ThreadText: # Reinforcement Learning with long term rewards and fixed states and actions
  
  (Asked by: username_0 on 2019-03-20)
  
  I have read a lot about RL algorithms, that update the action-value function at each step with the currently gained reward. The requirement here is, that the reward is obtained after each step.
  
  I have a case, where I have three steps, that have to be passed in a specific order. At each step the agent has to make a choice between a range of actions. The actions are specific for each step.
  
  To give an example for my problem:
  I want the algorithm to render a sentence of three words. For the first word the agent may choose a word out of `['I', 'Trees']`, the second word might be `['am', 'are']` and the last word could be chosen from `['nice', 'high']`. After the agent has made its choices, the reward is obtained once for the whole sentence.
  
  *Does anyone know which algorithms to use in this kind of problem?*
  
  ---
  
  To give a bit more detail on what I already tried:
  
  I thought that using value iteration would be an reasonable approach to test. My problem here is that I don't know how to assign the discounted reward for the chosen operations.
  
  For example after the last choice I get a reward of 0.9. But how do I update the value for the first action (choosing out of I and Trees in my example)?
  
  **Tags:** reinforcement-learning, rewards
  > **Comments:**
  > **username_1**: Why do you specifically want to use RL. These type of tasks are done by RNN and LSTM.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-03-21. Score: 4 | Accepted answer
  
  You are describing a straightforward Markov Decision Process that could be solved by almost any Reinforcement Learning algorithm.
  
  > I have read a lot about RL algorithms, that update the action-value function at each step with the currently gained reward. The requirement here is, that the reward is obtained after each step.
  
  This is true. However, the reward value can be zero, and it is quite common to have most states and actions result in zero reward with only some specific ones returning a non-zero value that makes a difference to the goals of the agent.
  
  When this is more extreme - e.g. only one non-zero reward per thousand steps - this is referred to as "sparse rewards" and can be a problem to handle well. Your three steps then reward situation is nowhere near this, and not an issue at all.
  
  > I thought that using value iteration would be an reasonable approach to test. My problem here is that I don't know how to assign the discounted reward for the chosen operations.
  
  Value iteration should be fine for your test problem, providing the number of choices for words is not too high.
  
  The way you assign discounted rewards is to use the Bellman equation as an update:
  
  $$v(s) \leftarrow \text{max}\_{a}[\sum\_{s',r} p(s',r|s,a)(r + \gamma v(s'))]$$
  
  For a deterministic environment you can simplify the sum, as $p(s',r|s, a)$ will be 1 for a specific combination of $s', r$
  
  It doesn't matter that $r = 0$ for the first two steps. The Bellman equation links time steps, by connecting $v(s)$ and $v(s')$. So, over many repetitions of value iteration's main loop, the episode end rewards get copied - with the discount applied - to their predecessor states. Very quickly in your case you will end up with values for the start states.
  
  > For example after the last choice I get a reward of 0.9. But how do I update the value for the first action (choosing out of I and Trees in my example)?
  
  You don't do it directly in a single step. What happens is repeating the value iteration loop copies the best values to their predecessor states, one possible time step at a time.
  
  On the first loop through all states, you will run an update something like:
  
  $$v(\text{'I'}) \leftarrow 0 + \gamma v(\text{'I am'})$$
  
  and $v(\text{'I am'}) = 0$ initially, so it will learn nothing useful in this first loop. However, it will also learn in the same loop:
  
  $$v(\text{'I am'}) \leftarrow 0 + \gamma v(\text{'I am nice'})$$
  
  So assuming $\gamma = 0.9$ and $v(\text{'I am nice'}) = 0.9$, and that "I am high" scores less than 0.9, then it will set $v(\text{'I am'}) = 0.81$.
  
  On the next loop through states in value iteration, it will then set $v(\text{'I'}) = 0.727$ (assuming "I am" beats "I are" for maximum value)
  
  > **Comments:**
  > **username_0**: But what if the value depends on the choices, that have been made? For exampe the value of ”am” is depending on the value of the other words. But imagine I take random actions and sample a bad set of actions so that ”am” is always chosen. Then ”am” might look like the best option, not being one. And even if i then generate samples where I choose the other action the value could already be biased, or am I wrong?  
  > **username_3**: @Jan: The value depending on other choices is not a problem in general, provided your state representation captures the differences (it does in this example). In value iteration, which you ask about, and which this answer uses, there is no sampling - just processing of all states and actions - so your missing sample cannot happen. However, in other solvers yes it is possible to at some stages have bad estimates because in order to learn accurate values, RL needs to sample enough variation. In tabular solvers that usually means sampling *all* variations enough times to make errors low.  
  > **username_0**: But this implies, that this approach is not suitable for bigger problems, where I do not have time to sample all variations (maybe even once). Which type of Agent would be suitable in that case?  
  > **username_0**: And another question: If I have to sample all variations enough times, is it not better to sample all possible variations (grid search like) and directly select the best?  
  > **username_3**: @Jan: That is correct, value iteration does not scale to large problems. This is too many extra questions though, and they are different to the main question - please ask a new question on the site if you want to know more.  
  
  ---
  
  ### Answer by username_2 on 2019-03-20. Score: 4
  
  You don't need to have a reward on every single timestep, reward at the end is enough. Reinforcement learning can deal with temporal credit assignment problem, all algorithms are designed to work with it. Its enough to define a reward at the end where you, for example, give a reward of 1 if sentence is satisfactory or -1 if it isn't. Regular tabular Q-learning would easily solve the toy problem that you gave as an example.
  
  > **Comments:**
  > **username_3**: I think this answer would be more complete, if rather than just asserting it will work, give an example answer to OP's question "But how do I update the value for the first action (choosing out of I and Trees in my example)?"  
  
  ---
  
  