Answers.Body: <p>When applying techniques like SARSA(which are on-policy), one needs to have control over a simulator. If one is able to access only the episodic dataset, then the only choice is to opt for Q-learning or Off-policy Monte-Carlo(or off-policy methods in general).</p>
  
  <blockquote>
    <p>Can a reward of zero
    be given in preliminary states before termination state of each
    episodes at which it will be rewarded with a positive/negative
    (win/loss) value?</p>
  </blockquote>
  
  <p>With regards to the above question, the answer is yes. The task would be a sparse reward task with a reward occurring only at the last transition. The issue that one faces in a sparse reward task is that of slow convergence(or even lack of convergence).</p>
  
  <p>Some guidelines for tackling sparse reward tasks are as follows :</p>
  
  <ol>
  <li><p><em>Monte-Carlo, and n-step Q-learning are preferred over Q-learning/SARSA.</em></p>
  
  <p>Consider the 10-step chain MDP, where the only reward is +1 when the transition from s10 to END occurs.
  <a href="https://i.sstatic.net/8JrW5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8JrW5.png" alt="enter image description here"></a></p>
  
  <p>Let us consider the first episode in training to be start->s1->s2->s3->....->s10->end. The Q-learning update would result in no sane updates to states s1, s2, s3, s9 because the Q-value of the next state is random-value. The only state with a sane update is s10</p>
  
  <p>However, if we use n-step Q-learning or a Monte-Carlo based update. The Q-values of all the states are updated in a logical manner since the reward from the end of the episode <em>propagates</em> to all states in the episode. </p>
  
  <p>n-step Q-learning would be ideal since by adjusting the value of <em>n</em>, one can trade-off the benefits of Monte-Carlo methods(described above) and Q-learning(low variance). </p></li>
  <li><p><em>The use of pseudo/auxiliary rewards</em>. </p>
  
  <p>This is not something necessarily recommended since the addition of new reward-structures can cause unintended behaviour. On the flip-side, it could lead to faster convergence. </p>
  
  <p>A simple example is as follows: Consider a game of chess, where the only reward is at the end of the game. Since the game of chess has very long episodes, one can introduce the following reward-structure instead :</p>
  
  <ul>
  <li>+100 for winning the game</li>
  <li>+1 for capturing any piece on the board</li>
  </ul>
  
  <p>Hence, the pseudo reward may provide some direction for learning. Note the different scales in the two rewards(100:1). This is necessary because the primary goal of the task should not shift to capturing pieces, but to win the match.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-13T07:55:57.340Z
Answers.LastActivityDate: 2018-01-13T20:28:09.730Z
Answers.LastEditDate: 2018-01-13T20:28:09.730Z
Answers.UserDisplayName: Rahul
Body: <p>I have some episodic datasets extracted from a turn-based RTS game in which the current actions leading to the next state doesn’t determine the final solution/outcome of the episode.</p>
  <p>The learning is expected to terminate at a final state/termination condition (when it wins or loses) for each episode and then move on to the next number of episodes in the dataset.</p>
  <p>I have being looking into Q learning, Monte Carlo and SARSA but I am confused about which one is most applicable.</p>
  <p>If any of the above algorithms are implemented, can a reward of zero be given in preliminary states before the termination state, at which it will be rewarded with a positive/negative (win/loss) value?</p>
  
Tags: <reinforcement-learning><game-ai><unsupervised-learning><monte-carlo-tree-search><q-learning>
Title: Which Reinforcement Learning algorithms are efficient for episodic problems?
UserDisplayName: Zadiq
ThreadText: # Which Reinforcement Learning algorithms are efficient for episodic problems?
  
  (Asked by: username_0 on 2018-01-13)
  
  I have some episodic datasets extracted from a turn-based RTS game in which the current actions leading to the next state doesn’t determine the final solution/outcome of the episode.
  
  The learning is expected to terminate at a final state/termination condition (when it wins or loses) for each episode and then move on to the next number of episodes in the dataset.
  
  I have being looking into Q learning, Monte Carlo and SARSA but I am confused about which one is most applicable.
  
  If any of the above algorithms are implemented, can a reward of zero be given in preliminary states before the termination state, at which it will be rewarded with a positive/negative (win/loss) value?
  
  **Tags:** reinforcement-learning, game-ai, unsupervised-learning, monte-carlo-tree-search, q-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-01-13. Score: 3 | Accepted answer
  
  When applying techniques like SARSA(which are on-policy), one needs to have control over a simulator. If one is able to access only the episodic dataset, then the only choice is to opt for Q-learning or Off-policy Monte-Carlo(or off-policy methods in general).
  
  > Can a reward of zero
  > be given in preliminary states before termination state of each
  > episodes at which it will be rewarded with a positive/negative
  > (win/loss) value?
  
  With regards to the above question, the answer is yes. The task would be a sparse reward task with a reward occurring only at the last transition. The issue that one faces in a sparse reward task is that of slow convergence(or even lack of convergence).
  
  Some guidelines for tackling sparse reward tasks are as follows :
  
  1. *Monte-Carlo, and n-step Q-learning are preferred over Q-learning/SARSA.*
  
     Consider the 10-step chain MDP, where the only reward is +1 when the transition from s10 to END occurs.
     [![enter image description here](https://i.sstatic.net/8JrW5.png)](https://i.sstatic.net/8JrW5.png)
  
     Let us consider the first episode in training to be start->s1->s2->s3->....->s10->end. The Q-learning update would result in no sane updates to states s1, s2, s3, s9 because the Q-value of the next state is random-value. The only state with a sane update is s10
  
     However, if we use n-step Q-learning or a Monte-Carlo based update. The Q-values of all the states are updated in a logical manner since the reward from the end of the episode *propagates* to all states in the episode.
  
     n-step Q-learning would be ideal since by adjusting the value of *n*, one can trade-off the benefits of Monte-Carlo methods(described above) and Q-learning(low variance).
  2. *The use of pseudo/auxiliary rewards*.
  
     This is not something necessarily recommended since the addition of new reward-structures can cause unintended behaviour. On the flip-side, it could lead to faster convergence.
  
     A simple example is as follows: Consider a game of chess, where the only reward is at the end of the game. Since the game of chess has very long episodes, one can introduce the following reward-structure instead :
  
     * +100 for winning the game
     * +1 for capturing any piece on the board
  
     Hence, the pseudo reward may provide some direction for learning. Note the different scales in the two rewards(100:1). This is necessary because the primary goal of the task should not shift to capturing pieces, but to win the match.
  
  
  ---
  
  