Reinforcement Learning: does sarsa still converge when policy changes during each episode 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.
 A: 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.
