ML//RL//Q-learning
Q-learning is a model-free reinforcement learning algorithm that learns the value \(Q(s,a)\) of taking action \(a\) in state \(s\) from experienced transitions alone, and it is used where a system can be tried (usually in a simulator) but its transition probabilities and rewards are unknown. It is the cleanest form of reinforcement learning: a table with one number per state-action pair, and one update rule.
Q-learning is a model-free reinforcement learning algorithm that learns the value Q(s,a)Q(s,a)Q(s,a) of taking action aaa in state sss from experienced transitions alone, and it is used where a system can be tried (usually in a simulator) but its transition probabilities and rewards are unknown. It is the cleanest form of reinforcement learning: a table with one number per state-action pair, and one update rule.
Picture a warehouse robot choosing aisles. It has no table of how often each aisle is congested, but every trip hands it one transition: it was in sss, took aaa, received rrr and landed in s′s's′. It then moves its entry a little toward what the Bellman equation says that entry should be:
Q(s,a)←Q(s,a)+α[ r+γmaxa′Q(s′,a′)−Q(s,a) ]Q(s,a) \leftarrow Q(s,a) + \alpha\big[\,r + \gamma \max_{a'} Q(s',a') - Q(s,a)\,\big]Q(s,a)←Q(s,a)+α[r+γa′maxQ(s′,a′)−Q(s,a)]
The bracket is the temporal-difference error, α\alphaα the learning rate and γ\gammaγ the discount factor. The target uses the best next action whatever the robot actually does next (the method is off-policy), so it can learn the optimal values while still exploring. The policy then falls out of the table: in each state, the action with the largest QQQ.
With enough visits to every state-action pair and a learning rate that decays suitably, tabular Q-learning converges to the optimal values. That condition is the catch, because every pair must be tried again and again: an ε\varepsilonε-greedy agent takes a random action a fraction ε\varepsilonε of the time, paying in reward for what it learns (exploration-exploitation trade-off).
It replaces the model by samples. Value iteration sweeps the same Bellman equation with P(s′∣s,a)P(s'\mid s,a)P(s′∣s,a) and RRR in hand; Q-learning estimates the expectation one experienced transition at a time. When a model exists, value iteration or dynamic programming gets there with far less data and no exploration risk.
The table only fits small discrete problems. A drone's state is continuous and has a dozen dimensions (curse of dimensionality); there a neural network approximates QQQ (the deep Q-network that learned Atari games from pixels in 2015), and the convergence guarantee goes away with the table.