I am currently learning about the Q-learning algorithm, so I therefore assume that it has some use or purpose. However I currently cannot see how it is in any way useful. In terms of complexity class, it appears to perform equal to or worse than brute force, which as far as I am aware, is the lowest you ever need to go to compute something computable.

What, if anything, have I missed?

  • $\begingroup$ "I am currently learning about the Q-learning algorithm, so I therefore assume that it has some use or purpose." -- Not necessarily. It may just be used didactically to make a point. $\endgroup$ – Raphael Feb 11 '14 at 11:39
  • 1
    $\begingroup$ @Raphael Well that is a purpose then. $\endgroup$ – 930913 Feb 11 '14 at 12:19
  • $\begingroup$ I'm glad you agree! :) $\endgroup$ – Raphael Feb 11 '14 at 15:46
  • $\begingroup$ As it is this question doesn't make any sense. You need to define what you mean by brute force in this scenario. Are you assuming you're given all the transition probabilities and rewards probabilities beforehand (note, this is wildly different then the assumption made in scenarios where Q-learning would be applied)? How does "brute force" deal with stochastic environments? etc etc. $\endgroup$ – alto Feb 11 '14 at 19:56
  • 1
    $\begingroup$ @930913 Another thing worth noting is you can use Q-learning in an online setting, which is the setup most people who study reinforcement learning are interested in. $\endgroup$ – alto Feb 12 '14 at 0:53

Reinforcement Learning (RL) algorithms are useful in a setting when the structure of the environment is unknown and/or stochastic. The environment is normally formalized as a Markov Decision Process (MDP) or Partially Observable Markov Decision Process (POMDP) and the goal of an RL agent is then to maximize its cumulative reward (or minimize its regret with respect to the best alternate policy) while behaving in the environment.

As such it isn't clear how a brute force algorithm would efficiently deal with the stochastic nature of the environment or the fact that this procedure is almost universally assumed to be done online. For more information and a modern overview of RL I recommend this excellent reference by Csaba Szepesvari.


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.