5

I keep coming across this term when reading about reinforcement learning, for example in this sentence:

If the problem is modelled with care, some Reinforcement Learning algorithms can converge to the global optimum

http://reinforcementlearning.ai-depot.com/

or here:

For any fixed policy Pi, the TD algorithm described above has been proved to converge to VPi

http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node62.html

My understanding of the word converge is that it means several things coming together to the same point, but how can a single thing (the algorithm) do that?

  • 6
    In the case of iterative algorithms, they are said to converge when their candidate solutions for each iteration tend to get closer and closer to the desired solution. – MetaFight Jul 5 '15 at 17:05
  • 4
    It may help to recall that a limit in mathematics is also said to either converge or diverge, even though a "limit" is a "single thing". – Ixrec Jul 5 '15 at 17:14
8

An iterative algorithm is said to converge when, as the iterations proceed, the output gets closer and closer to a specific value. More precisely, no matter how small an error value you choose, if you continue long enough the function will eventually stay closer than that error value from some final value.

In some circumstances, an algorithm will not converge; it could even diverge, where its output will undergo larger and larger oscillations, never approaching a useful result. More precisely, no matter how long you continue, the function value will never settle down within a range of any "final" value.

The "converge to a global optimum" phrase in your first sentence is a reference to algorithms which may converge, but not to the "optimal" value (e.g. a hill-climbing algorithm which, depending on initial conditions, may converge to a local maximum, never reaching the global maximum).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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