Answers.Body: <p>You are correct: to evaluate a policy, we need to fix it.</p>
  <ul>
  <li>We can <em>temporarily</em> fix it, just to evaluate it over a number of test cases. For a fair comparison, we should fix the start states and random seeds used for the transitions.</li>
  <li>We can wait until convergence / until we are satisfied. The resulting policy would be what we implement in the &quot;true&quot;, trained agent. This is important when exploration might be harmful in the &quot;real world&quot; domain where the agent will be operating.</li>
  <li>We can also measure average reward of the &quot;non-stationary&quot; policy, and assume that, once the agent is doing well, this should be close enough to evaluating the fixed policy. This is not ideal, but on the other hand it is trivial to implement, and is often used to track the learning process. If you have a life-long learning agent, this might be the best you can do.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T06:46:31.540Z
Answers.Text: if we wait until convergence to calculate $r(\pi)$, then how are we using $r(\pi)$ to find optimal policy.
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T06:53:32.117Z
Answers.Text: When finding the optimal policy, we're not using $r(\pi)$, but we might be using $Q(s, a, \pi)$ when we're using policy iteration. In policy iteration we fix the policy until the values have converged, and then improve the policy.
  When we use other methods where the policy changes, we use the $Q(s, a)$ values that do depend on the exploration policy, but eventually converge; that's what the Bellman equations tell us. Of course, this assumes that we're using a table-based approach. When using function approximation, we have no guarantees of convergence.
Answers.UserDisplayName: Robby Goetschalckx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T08:16:34.037Z
Answers.Text: you said that, "when finding the optimal policy we are not using $r(\pi)$, but in the above SARSA algorithm we are compensating $w$ using $r(\pi)$ also that changes our policy per iteration. I think what you are trying to say is that use it like policy iteration algorithm. But in the above algorithm I can't see update like this.
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T13:09:48.553Z
Answers.Text: The SARSA algorithm does not mention $\pi$ anywhere. It is not evaluating a fixed policty. It does not try to learn $Q(s, a, \pi)$. It will learn $Q(s, a)$ (the *actual* $Q$-values). This particular algorithm does so by trying to steer the weights of the policy in such a way that the average reward is maximized (that's where the gradient comes in).
Answers.UserDisplayName: Robby Goetschalckx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T13:50:36.853Z
Answers.Text: Yes, it will try to maximize the average reward. But my question was, how are we calculating the average reward while changing the policy over every step (here policy is $\epsilon$-greedy).
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-28T13:57:01.143Z
Answers.Text: The algorithm itself does not calculate the average reward explicitly -- it uses the Q-values. Maximizing the Q value (by tweaking your policy parameters for a given state) will implicitly improve the total average reward of the policy, as well.
Answers.UserDisplayName: Robby Goetschalckx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-27T21:17:20.497Z
Answers.LastActivityDate: 2020-08-27T21:17:20.497Z
Answers.UserDisplayName: Robby Goetschalckx
Body: <p>In the average reward setting, the quality of a policy is defined as:
  <span class="math-container">$$ r(\pi) = \lim_{h\to\infty}\frac{1}{h} \sum_{j=1}^{h}E[R_j] $$</span>
  When we reach the steady state distribution, we can write the above equation as follows:
  <span class="math-container">$$ r(\pi) = \lim_{t\to\infty}E[R_t | A \sim \pi] $$</span>
  We can use the incremental update method to find <span class="math-container">$r(\pi)$</span>:
  <span class="math-container">$$ r(\pi) = \frac{1}{t} \sum_{j=1}^{t} R_j = \bar R_{t-1} + \beta (R_t - \bar R_{t-1})$$</span>
  where <span class="math-container">$ \bar R_{t-1}$</span> is the estimate of the average reward <span class="math-container">$r(\pi)$</span> at time step <span class="math-container">$t-1$</span>.
  We use this incremental update rule in the SARSA algorithm:
  <a href="https://i.sstatic.net/BFJor.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/BFJor.png" alt="enter image description here" /></a></p>
  <p>Now, in this above algorithm, we can see that the policy will change with respect to time. But to calculate the <span class="math-container">$r(\pi)$</span>, the agent should follow the policy <span class="math-container">$\pi$</span> for a long period of time. Then how we are using <span class="math-container">$r(\pi)$</span> if the policy changes with respect to time?</p>
  
Tags: <reinforcement-learning><deep-rl><sarsa>
Title: How are we calculating the average reward ($r(\pi)$) if the policy changes over time?
UserDisplayName: Swakshar Deb
ThreadText: # How are we calculating the average reward ($r(\pi)$) if the policy changes over time?
  
  (Asked by: username_0 on 2020-08-27)
  
  In the average reward setting, the quality of a policy is defined as:
  $$ r(\pi) = \lim\_{h\to\infty}\frac{1}{h} \sum\_{j=1}^{h}E[R\_j] $$
  When we reach the steady state distribution, we can write the above equation as follows:
  $$ r(\pi) = \lim\_{t\to\infty}E[R\_t | A \sim \pi] $$
  We can use the incremental update method to find $r(\pi)$:
  $$ r(\pi) = \frac{1}{t} \sum\_{j=1}^{t} R\_j = \bar R\_{t-1} + \beta (R\_t - \bar R\_{t-1})$$
  where $ \bar R\_{t-1}$ is the estimate of the average reward $r(\pi)$ at time step $t-1$.
  We use this incremental update rule in the SARSA algorithm:
  [![enter image description here](https://i.sstatic.net/BFJor.png)](https://i.sstatic.net/BFJor.png)
  
  Now, in this above algorithm, we can see that the policy will change with respect to time. But to calculate the $r(\pi)$, the agent should follow the policy $\pi$ for a long period of time. Then how we are using $r(\pi)$ if the policy changes with respect to time?
  
  **Tags:** reinforcement-learning, deep-rl, sarsa
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-27. Score: 2
  
  You are correct: to evaluate a policy, we need to fix it.
  
  * We can *temporarily* fix it, just to evaluate it over a number of test cases. For a fair comparison, we should fix the start states and random seeds used for the transitions.
  * We can wait until convergence / until we are satisfied. The resulting policy would be what we implement in the "true", trained agent. This is important when exploration might be harmful in the "real world" domain where the agent will be operating.
  * We can also measure average reward of the "non-stationary" policy, and assume that, once the agent is doing well, this should be close enough to evaluating the fixed policy. This is not ideal, but on the other hand it is trivial to implement, and is often used to track the learning process. If you have a life-long learning agent, this might be the best you can do.
  
  > **Comments:**
  > **username_0**: if we wait until convergence to calculate $r(\pi)$, then how are we using $r(\pi)$ to find optimal policy.  
  > **username_1**: When finding the optimal policy, we're not using $r(\pi)$, but we might be using $Q(s, a, \pi)$ when we're using policy iteration. In policy iteration we fix the policy until the values have converged, and then improve the policy. When we use other methods where the policy changes, we use the $Q(s, a)$ values that do depend on the exploration policy, but eventually converge; that's what the Bellman equations tell us. Of course, this assumes that we're using a table-based approach. When using function approximation, we have no guarantees of convergence.  
  > **username_0**: you said that, "when finding the optimal policy we are not using $r(\pi)$, but in the above SARSA algorithm we are compensating $w$ using $r(\pi)$ also that changes our policy per iteration. I think what you are trying to say is that use it like policy iteration algorithm. But in the above algorithm I can't see update like this.  
  > **username_1**: The SARSA algorithm does not mention $\pi$ anywhere. It is not evaluating a fixed policty. It does not try to learn $Q(s, a, \pi)$. It will learn $Q(s, a)$ (the *actual* $Q$-values). This particular algorithm does so by trying to steer the weights of the policy in such a way that the average reward is maximized (that's where the gradient comes in).  
  > **username_0**: Yes, it will try to maximize the average reward. But my question was, how are we calculating the average reward while changing the policy over every step (here policy is $\epsilon$-greedy).  
  > **username_1**: The algorithm itself does not calculate the average reward explicitly -- it uses the Q-values. Maximizing the Q value (by tweaking your policy parameters for a given state) will implicitly improve the total average reward of the policy, as well.  
  
  ---
  
  