Q-Learning

Q-learning is one of the most important algorithms in reinforcement learning. It learns a Q-function: a mapping from (state, action) pairs to their expected long-term value. Q(s, a) answers the question: "if I'm in state s and take action a, what is the best total cumulative reward I can expect from this point forward?" Once the Q-function is learned, the optimal policy is simple: in any state, take the action with the highest Q-value.

Q-learning is model-free: it learns Q-values directly from experience without needing to know the transition probabilities or reward function of the environment. The agent interacts with the environment, observes the state, takes an action, receives a reward, and observes the next state. It updates its Q estimate using the Bellman equation: Q(s,a) is updated toward r + gamma * max_a' Q(s', a'), where r is the immediate reward, gamma is the discount factor, and max_a' Q(s', a') is the best Q-value achievable from the next state.

This update rule has an elegant property: it is an off-policy algorithm. The agent can learn about the optimal policy while following a different (exploratory) policy. The exploratory policy tries actions that might not be optimal to gather information about the Q-values; the learning update still converges toward the optimal Q-values regardless of which policy the agent uses to collect data.

For environments with small, discrete state and action spaces, Q-learning can be implemented as a lookup table (a Q-table) that stores one Q-value per state-action pair. For Tic-Tac-Toe or small grid worlds, Q-tables work well. For larger state spaces (Atari games, where states are raw pixel images), a Q-table is infeasible - there are too many states to enumerate. Deep Q-Networks (DQN) replace the Q-table with a neural network that takes a state as input and outputs Q-values for all actions.

Convergence of Q-learning (to the optimal Q-function) is guaranteed under tabular conditions if all state-action pairs are visited infinitely often and the learning rate satisfies standard diminishing conditions. The exploration-exploitation tradeoff determines how the agent balances trying new actions (to discover better strategies) versus exploiting known good actions. Epsilon-greedy exploration - taking a random action with probability epsilon, otherwise taking the greedy best action - is the simplest and most widely used strategy.

Double Q-learning addresses a systematic overestimation bias in standard Q-learning: using the same Q-function to both select and evaluate actions produces optimistic value estimates. Double Q-learning uses two Q-networks: one to select the best action, another to evaluate its value, decorrelating the two operations.