An introduction to Q-learning
Q-learning [Watkins, 1989] is one of the most popular reinforcement learning methods. One of the advantages of Q-learning is its ability to compare the expected utility of the available actions without requiring a model of the environment.
The basic content of Q-learning is inside the below equation:
![Q_{t+1}(a, s)=(1-\alpha_{t})Q_{t}(a,s)+\alpha_{t}[r_{t}(s)+\gamma\max_{a^{'}}{Q_{t}(a',s')}]](http://s.wordpress.com/latex.php?latex=Q_%7Bt%2B1%7D%28a%2C%20s%29%3D%281-%5Calpha_%7Bt%7D%29Q_%7Bt%7D%28a%2Cs%29%2B%5Calpha_%7Bt%7D%5Br_%7Bt%7D%28s%29%2B%5Cgamma%5Cmax_%7Ba%5E%7B%27%7D%7D%7BQ_%7Bt%7D%28a%27%2Cs%27%29%7D%5D&bg=ffffff&fg=000000&s=0 "Q_{t+1}(a, s)=(1-\alpha_{t})Q_{t}(a,s)+\alpha_{t}[r_{t}(s)+\gamma\max_{a^{'}}{Q_{t}(a',s')}]")
Where:
is the Q-value at time
, state
with action
.
is the reward.
is the learning rate. The learning rate determines how fast and how important the new information is to be learned. If
is the discount factor. The discount factor is in range [0..1] and is used to weight new term reinforcement more heavily than distant future reinforcement. The closer
So what does the equation mean ? We now assume 
It is now easy to see that the Q-value of state-action pair (
When the discount factor is enabled (<1), it makes the reward reduced by time and hence the total reward at time
The bellow java applet is a very good illustration of Q-learning (thank to Vander B. Frank):
For the detail of how the applet works, please reach the document of Vander B. Frank through this PDF.
Bibliography
1. Wikipedia: Q-learning [http://en.wikipedia.org/wiki/Q-learning].
2. Vander B. Frank: Q-learning. IRIDIA, Universit Libre de Bruxelles. 7, 2003. [PDF]
3. Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England