3
$\begingroup$

I am using Q-learning and SARSA to solve a problem. The agent learns to go from the start to the goal without falling in the holes.

At each state, I can choose the action corresponding to the maximum Q value at the state (the greedy action that the agent would take). And all the actions connect some states together. I think that would show me a road from start to goal, which means the result converges.

But some others think that as long as the agent learns how to reach the goal, the result converges. Sometimes the success rate is very high but we cannot get the road from Q table. I don't know which one means the agent is trained totally and what the converged result means.

$\endgroup$
4
$\begingroup$

A typical and practical way to measure the convergence to some solution (so not necessarily the optimal one!) of any numerical iterative algorithm (such as RL algorithms) is to check if the current solution has not changed (much) with respect to the previous one. In your case, the solutions are value functions, so you could check if your algorithm has converged to some value function e.g. as follows

$$ c(q_t, q_{t-1}, \epsilon) = \begin{cases} 1, &\text{if } |q_t(s, a) - q_{t-1}(s, a)| < \epsilon, \forall s \in S, a \in A \\ 0, & \text{otherwise} \end{cases}, \tag{1}\label{1} $$ where

  • $c$ is the "convergence" function (aka termination condition) that returns $1$ (true) if your RL algorithm has converged to some small enough neighbourhood of value functions (where those value functions are "indistinguishable"), and $0$ otherwise
  • $q_t$ is the value function at iteration $t$
  • $\epsilon$ is a threshold (aka precision or tolerance) value, which is a hyper-parameter that you can set depending on your "tolerance" (hence the name); this value is typically something like $10^{-6}$

Of course, this requires that you keep track of two value functions.

You can also define your "convergence" function $c$ in \ref{1} differently. For example, rather than using the absolute value, you could use the relative error, i.e. $\left|\frac{q_t(s, a) - q_{t-1}(s, a)}{q_t(s, a)} \right|$. Moreover, given that RL algorithms are exploratory (i.e. stochastic) algorithms, the value function may not change (much) from one iteration to the other, but, in the next one, it could significantly change because of your exploratory/behavioural actions, so you may also want to take into account more iterations, i.e. after e.g. $N > 1$ iterations, if the value function does not change much, then you could say (maybe probabilistically) that your RL algorithm has converged to some small neighbourhood of value functions in the space of value functions.

Note that these approaches do not guarantee that your RL algorithm has converged to the global optimal value function, but to some locally optimal value function (or, more precisely, small neighborhood of value functions). Q-learning is guaranteed to converge to the optimal value function in the tabular setting (your setting), but this is in the limit; in practice, it is more difficult to know if Q-learning has converged to an optimal or near-optimal value function.

Maybe you can also have a look at episodic returns of the policy derived from your final value function, but without upper and lower bounds on the optimal returns, you don't know much about the global optimality of your policy/value function.

Yes, you can check if the policy makes the agent reach the goal, but many policies could do that job, i.e. that does not say that the policy is the best (or optimal) one, i.e. that's a necessary (provided the goal is reachable and the reward function models your actual goal) but not sufficient condition (for optimality). The optimality here is usually a function of the return (given that is what you are usually trying to optimize).

$\endgroup$
  • $\begingroup$ This answer is based on my general knowledge of numerical algorithms and not much on how people (in the RL community) determine when their Q-learning (or, in general, RL) algorithms converge. It's possible that people may be using other approaches to determine the convergence in practice. Right now, I don't recall serious approaches: typically, they just comment on the collected returns/rewards plots. So, I encourage other people that are familiar with RL research to give other answers, if they know/remember other approaches. $\endgroup$ – nbro Oct 14 '20 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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