Answers.Body: <p>There are a couple of things to break down here.</p>
  
  <p>The first thing is to correct this:</p>
  
  <blockquote>
    <p>For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step <span class="math-container">$t$</span>.</p>
  </blockquote>
  
  <p>In a Markov Decision Process (MDP), there is always an immediate reward for each time <span class="math-container">$t$</span> from <span class="math-container">$t=1$</span> to <span class="math-container">$t=T$</span> (terminal state). This is the reward distribution that the algorithms refer to as <span class="math-container">$R_t$</span>. </p>
  
  <p>It does not matter if nearly all the rewards are <span class="math-container">$0$</span>. That is still a reward value, even if it is not an interesting or informative one. Some environments will have non-zero rewards on nearly all time steps. Some environments might have zero rewards for every transition apart from one or two important exceptions that define the goal of the agent.</p>
  
  <p>So in tic-tac-toe, if the game has not ended, the reward will be <span class="math-container">$0$</span> because neither player has won or lost, and obtaining a win is a learning objective. If you use <span class="math-container">$0$</span> reward value for all incomplete time steps in tic-tac-toe, and SARSA algorithm as written from Sutton &amp; Barto, then it will work as expected. You don't need to wait until the end of the episode, and the algorithm will still learn to predict values of moves despite experiencing many <span class="math-container">$r_t = 0$</span> during start and middle of the game.</p>
  
  <p>You show the MC prediction algorithm, which <em>does</em> wait until the end of each episode until calculating estimated values, using the experienced <em>return</em>.</p>
  
  <p>I think one of the things that you might want to review is the difference between <em>immediate reward</em> following a timestep (noted <span class="math-container">$R_{t+1}$</span>) and <em>return</em> (noted <span class="math-container">$G_t$</span>). There is a relationship between the two <span class="math-container">$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$</span>. All the value based methods, such as MC prediction, or SARSA, are ways to estimate the expected return <span class="math-container">$\mathbb{E}_{\pi}[G_t]$</span> given some context, such as the state or state and action at time <span class="math-container">$t$</span>.</p>
  
  <p>Given that, this should answer your other questions.</p>
  
  <blockquote>
    <p>Is determining the reward for each action a requirement of SARSA? </p>
  </blockquote>
  
  <p>It is a general requirement for MDPs, and is expected by all solvers. However, a default of <span class="math-container">$0$</span> is fine, if that's how the environment works. The reinforcement learning (RL) algorithms can all cope with delays to important reward values (such as those from winning or losing a game). Bigger delays - e.g. thousands of <span class="math-container">$0$</span> reward steps between more meaningful values - are often associated with harder problems to solve, so the simpler algorithms might not be practical. But they all cope in theory given enough experience.</p>
  
  <blockquote>
    <p>Can the agent wait until the end of the episode to determine the reward?</p>
  </blockquote>
  
  <p>No, you should always be able calulate an <em>immediate reward</em> value <span class="math-container">$r_{t+1}$</span> after taking each action <span class="math-container">$a_t$</span> from state <span class="math-container">$s_t$</span>. </p>
  
  <p>However, it is OK in general to wait until you have summed up more of those rewards (e.g. <span class="math-container">$r_{t+1}$</span> to <span class="math-container">$r_{t+n}$</span>) before making an estimate of the return <span class="math-container">$g_t$</span> to update a value estimate. Single step SARSA (sometimes called SARSA(0)) does not wait - it makes update steps using a single immediate reward value. However, other agent types including Monte Carlo (MC), and some variants of SARSA, can and do wait - sometimes just for some steps, sometimes until the end of each episode. </p>
  
  <p>It is a choice you can make when designing agents, there are consequences. Waiting until end of the episode (as in MC) means you have unbiased estimates of value, but takes longer, and leads to higher variability in updates. Using reward values after each step (as in SARSA(0)) means you get to make more frequent updates which may converge fatser, but you start with biased incorrect values.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-01T20:39:41.617Z
Answers.LastActivityDate: 2020-06-01T20:49:54.500Z
Answers.LastEditDate: 2020-06-01T20:49:54.500Z
Answers.UserDisplayName: Neil Slater
Body: <p>From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 99), the following definition for first-visit MC prediction, for estimating <span class="math-container">$V \sim V_\pi$</span> is given:</p>
  
  <p><a href="https://i.sstatic.net/J5aP2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/J5aP2.png" alt="enter image description here"></a></p>
  
  <p>Is determining the reward for each action a requirement of SARSA? Can the agent wait until the end of the episode to determine the reward? </p>
  
  <p>For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step <span class="math-container">$t$</span>. </p>
  
  <p>Does this mean then that depending on the task it is not always possible to determine reward at time step <span class="math-container">$t$</span>, and the agent must wait until the end of an episode? If the agent does not evaluate reward until the end of an episode, is the algorithm still SARSA?</p>
  
Tags: <reinforcement-learning><definitions><rewards><sarsa>
Title: Can the agent wait until the end of the episode to determine the reward in SARSA?
UserDisplayName: blue-sky
ThreadText: # Can the agent wait until the end of the episode to determine the reward in SARSA?
  
  (Asked by: username_0 on 2020-06-01)
  
  From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 99), the following definition for first-visit MC prediction, for estimating $V \sim V\_\pi$ is given:
  
  [![enter image description here](https://i.sstatic.net/J5aP2.png)](https://i.sstatic.net/J5aP2.png)
  
  Is determining the reward for each action a requirement of SARSA? Can the agent wait until the end of the episode to determine the reward?
  
  For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.
  
  Does this mean then that depending on the task it is not always possible to determine reward at time step $t$, and the agent must wait until the end of an episode? If the agent does not evaluate reward until the end of an episode, is the algorithm still SARSA?
  
  **Tags:** reinforcement-learning, definitions, rewards, sarsa
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-01. Score: 2 | Accepted answer
  
  There are a couple of things to break down here.
  
  The first thing is to correct this:
  
  > For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.
  
  In a Markov Decision Process (MDP), there is always an immediate reward for each time $t$ from $t=1$ to $t=T$ (terminal state). This is the reward distribution that the algorithms refer to as $R\_t$.
  
  It does not matter if nearly all the rewards are $0$. That is still a reward value, even if it is not an interesting or informative one. Some environments will have non-zero rewards on nearly all time steps. Some environments might have zero rewards for every transition apart from one or two important exceptions that define the goal of the agent.
  
  So in tic-tac-toe, if the game has not ended, the reward will be $0$ because neither player has won or lost, and obtaining a win is a learning objective. If you use $0$ reward value for all incomplete time steps in tic-tac-toe, and SARSA algorithm as written from Sutton & Barto, then it will work as expected. You don't need to wait until the end of the episode, and the algorithm will still learn to predict values of moves despite experiencing many $r\_t = 0$ during start and middle of the game.
  
  You show the MC prediction algorithm, which *does* wait until the end of each episode until calculating estimated values, using the experienced *return*.
  
  I think one of the things that you might want to review is the difference between *immediate reward* following a timestep (noted $R\_{t+1}$) and *return* (noted $G\_t$). There is a relationship between the two $G\_t = \sum\_{k=0}^{\infty} \gamma^k R\_{t+k+1}$. All the value based methods, such as MC prediction, or SARSA, are ways to estimate the expected return $\mathbb{E}\_{\pi}[G\_t]$ given some context, such as the state or state and action at time $t$.
  
  Given that, this should answer your other questions.
  
  > Is determining the reward for each action a requirement of SARSA?
  
  It is a general requirement for MDPs, and is expected by all solvers. However, a default of $0$ is fine, if that's how the environment works. The reinforcement learning (RL) algorithms can all cope with delays to important reward values (such as those from winning or losing a game). Bigger delays - e.g. thousands of $0$ reward steps between more meaningful values - are often associated with harder problems to solve, so the simpler algorithms might not be practical. But they all cope in theory given enough experience.
  
  > Can the agent wait until the end of the episode to determine the reward?
  
  No, you should always be able calulate an *immediate reward* value $r\_{t+1}$ after taking each action $a\_t$ from state $s\_t$.
  
  However, it is OK in general to wait until you have summed up more of those rewards (e.g. $r\_{t+1}$ to $r\_{t+n}$) before making an estimate of the return $g\_t$ to update a value estimate. Single step SARSA (sometimes called SARSA(0)) does not wait - it makes update steps using a single immediate reward value. However, other agent types including Monte Carlo (MC), and some variants of SARSA, can and do wait - sometimes just for some steps, sometimes until the end of each episode.
  
  It is a choice you can make when designing agents, there are consequences. Waiting until end of the episode (as in MC) means you have unbiased estimates of value, but takes longer, and leads to higher variability in updates. Using reward values after each step (as in SARSA(0)) means you get to make more frequent updates which may converge fatser, but you start with biased incorrect values.
  
  
  ---
  
  