3
$\begingroup$

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

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
6
  • $\begingroup$ if we wait until convergence to calculate $r(\pi)$, then how are we using $r(\pi)$ to find optimal policy. $\endgroup$
    – Swakshar Deb
    Commented Aug 28, 2020 at 6:46
  • $\begingroup$ 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. $\endgroup$
    – Robby Goetschalckx
    Commented Aug 28, 2020 at 6:53
  • $\begingroup$ 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. $\endgroup$
    – Swakshar Deb
    Commented Aug 28, 2020 at 8:16
  • $\begingroup$ 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). $\endgroup$
    – Robby Goetschalckx
    Commented Aug 28, 2020 at 13:09
  • $\begingroup$ 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). $\endgroup$
    – Swakshar Deb
    Commented Aug 28, 2020 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .