2
$\begingroup$

I use n-step Sarsa/sometimes Sarsa($\lambda$) to solve a maze problem.

After experimenting a bit with different epsilon schedules I found out that the agent learns faster when I change the epsilon during an episode based on the number of steps already taken and the mean length of the last 10 episodes.

Low number of steps/beginning of episode => Low epsilon
High number of steps/end of episode => High epsilon

This works far better than just an epsilon decay over time from episode to episode.

Does the theory allow this?

I think yes because all states are still visited regularly.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

All variants of SARSA are on-policy algorithms. This means that they learn Q-values for the policy that they are also following to generate experience.

If you want theoretical guarantees for convergence, this means that you should eventually settle down on a single policy, such that your Q values can converge to the values that are optimal for that policy. For example, a typical assumption is Greedy in the Limit with Infinite Exploration (GLIE), which means that you keep infinite exploration, but also tend towards a greedy policy in the limit. This seems a bit contradictory, but is possible with $\epsilon = \frac{1}{t}$ for example, where $t$ are your timesteps.

That's only required if you want to converge to an "optimal" greedy policy though. If you keep $\epsilon$ constant at $0.1$ for example, your Q values will still converge, they'll just converge to a different notion of optimality; they'll converge to values that are optimal given the knowledge that you'll act randomly 10% of the time.

Now, you describe varying $\epsilon$ as follows:

I change the epsilon during an episode based on the number of steps already taken and the mean length of the last 10 episodes.

Low number of steps/beginning of episode => Low epsilon

High number of steps/end of episode => High epsilon

This certainly isn't GLIE, it's not going to converge to the most obvious notion of optimality (greedy). It might still converge to something (something that's not trivial to understand) if the way you're varying $\epsilon$ eventually settles down to a... "consistent" manner of varying it. For example, if your $\epsilon$ were consistently the same (deterministic or nondeterministic) function of the state $S_t$, e.g. $\epsilon = f(S_t)$, I could see SARSA being able to converge to some policy that is optimal given knowledge of that consistent style of exploration. I don't think that the way that you describe for varying $\epsilon$ satisfies that. Varying it based on the number of steps taken inside the episode is questionable (e.g. $\epsilon = f(t)$ for some function $f$), unless you incorporate $t$ in the state representation (which is typically not done). Varying $\epsilon$ based on things that happened in previous episodes is definitely going to be problematic for convergence, it means your episodes are no longer independent.

That said, it's still possible you observe improved performance in practice. Convergence guarantees in Reinforcement Learning always make assumptions like "infinite exploration" and "an infinite amount of time". Those are assumptions that are never going to be satisfied in practice, noone has an infinite amount of time. So, convergence properties don't tell the full story, performance in practice can be different.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's true episodes are no longer independent. Now, I also decay epsilon after every timestep on top of the already mentioned rules. Episodes are still not independent, but it just works so damn well. At some point, I need to provide a reason why I am allowed to do this. It won't be easy to show theoretically to what kind of policy this scheme converges. Do you know a similar epsilon schedule which works usually better than standard decayed epislon and also has a better theoretical foundation? RL promised to be the one fits all solution and now every problem needs individual treatment... $\endgroup$
    – siva
    Commented Apr 11, 2018 at 7:35
  • 1
    $\begingroup$ @Jan Nope I'm not familiar with better epsilon schedules. $\epsilon$ already generally is just a hyperparameter that needs tuning, even if you're not doing anything special with it. Tweaking it based on what happened in earlier episodes can be viewed just as adjusting that initial setting. I do think it makes sense intuitively. Episode length in recent episodes is some sort of measure of how well you're doing, and it makes sense to adjust your exploration according to how well you're doing. Proofs are gonna be difficult though $\endgroup$
    – Dennis Soemers
    Commented Apr 11, 2018 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.