CtrlK
The Q-function, also called the action-value function or state-action value function, is a core concept in reinforcement learning (RL). It maps a state-action pair to a scalar value representing the expected cumulative discounted reward an agent will receive by taking a particular action in a given state and then following a specific policy thereafter. Denoted Q(s, a), the Q-function serves as the foundation for a large family of RL algorithms, including Q-learning, Deep Q-Networks, and Soft Actor-Critic.
Imagine you are playing a board game, and in every square you land on, you can pick from a few different moves. The Q-function is like a cheat sheet that tells you, "If you are on this square and you pick this move, here is how many points you can expect to earn by the end of the game." At first, the cheat sheet is blank because you have never played before. Every time you play and see what happens after a move, you update the cheat sheet a little bit. After many games, the cheat sheet becomes very accurate, and you can just look at it to pick the best move every time.
Sometimes, the board is so big that writing down every single square and move would fill an entire library. In that case, you train a computer brain (a neural network) to memorize the patterns on the cheat sheet instead of writing everything down. That is what a Deep Q-Network does.
Given a Markov decision process (MDP) defined by a tuple (S, A, P, R, gamma), where S is the state space, A is the action space, P is the state-transition probability function, R is the reward function, and gamma is the discount factor (0 <= gamma < 1), the Q-function under a policy pi is defined as:
Q^pi(s, a) = E_pi [ sum_{t=0}^{infinity} gamma^t * R(s_t, a_t) | s_0 = s, a_0 = a ]
Here, E_pi denotes the expectation over trajectories generated by following policy pi after taking action a in state s. The discount factor gamma controls the trade-off between immediate and future rewards. When gamma is close to 0, the agent behaves myopically, prioritizing immediate rewards. When gamma is close to 1, the agent gives nearly equal weight to distant future rewards.
The optimal Q-function, denoted Q*(s, a), corresponds to the Q-function under the optimal policy pi*:
Q*(s, a) = max_pi Q^pi(s, a)
Once Q* is known, an optimal policy can be recovered simply by choosing the action with the highest Q-value in each state:
pi*(s) = argmax_a Q*(s, a)
The Q-function is closely related to two other functions that appear throughout reinforcement learning theory.
| Function | Notation | Definition | Depends on |
|---|---|---|---|
| State-value function | V^pi(s) | Expected return starting from state s and following policy pi | State only |
| Action-value function (Q-function) | Q^pi(s, a) | Expected return starting from state s, taking action a, then following pi | State and action |
| Advantage function | A^pi(s, a) | How much better action a is compared to the average action under pi | State and action |
The state-value function V^pi(s) gives the expected return from state s under policy pi. It relates to the Q-function by marginalizing over actions:
V^pi(s) = sum_a pi(a|s) * Q^pi(s, a)
For the optimal value function, V*(s) = max_a Q*(s, a).
The advantage function measures the relative benefit of taking a specific action over the average:
A^pi(s, a) = Q^pi(s, a) - V^pi(s)
The advantage function is used in algorithms such as Advantage Actor-Critic (A2C) and Dueling DQN to reduce variance in value estimates. By construction, the advantage of the best action under pi is non-negative, and the expected advantage across all actions under the policy is zero.
The Q-function satisfies a recursive relationship known as the Bellman equation, which decomposes the value of a state-action pair into an immediate reward plus the discounted expected future value.
For a given policy pi:
Q^pi(s, a) = R(s, a) + gamma * sum_{s'} P(s'|s, a) * sum_{a'} pi(a'|s') * Q^pi(s', a')
This equation states that the Q-value of taking action a in state s equals the immediate reward plus the discounted Q-value of the next state-action pair, averaged over the transition dynamics and the policy. When the state and action spaces are finite and the transition dynamics are known, this forms a system of linear equations that can be solved exactly.
The optimal Q-function satisfies a nonlinear version of the Bellman equation:
Q*(s, a) = R(s, a) + gamma * sum_{s'} P(s'|s, a) * max_{a'} Q*(s', a')
The key difference from the expectation equation is the max operator: instead of averaging over actions according to a policy, the agent selects the action that yields the highest Q-value. This nonlinear system requires iterative algorithms (such as value iteration or Q-learning) to solve.
Q-learning, introduced by Christopher Watkins in his 1989 PhD thesis "Learning from Delayed Rewards" at the University of Cambridge, is a model-free, off-policy algorithm that learns the optimal Q-function directly from experience without requiring knowledge of the environment's transition dynamics.
The agent maintains a table of Q-values (one entry per state-action pair) and updates them after each transition using temporal difference (TD) learning:
Q(s, a) <- Q(s, a) + alpha * [ R + gamma * max_{a'} Q(s', a') - Q(s, a) ]
In this equation:
Watkins and Dayan (1992) proved that tabular Q-learning converges to the optimal Q-function Q* with probability 1, provided that:
These conditions ensure that the algorithm explores enough of the state-action space and that the updates diminish over time, preventing oscillation.
Initialize Q(s, a) arbitrarily for all s in S, a in A
For each episode:
Initialize state s
Repeat for each step:
Choose action a from s using policy derived from Q (e.g., epsilon-greedy)
Take action a, observe reward R and next state s'
Q(s, a) <- Q(s, a) + alpha * [R + gamma * max_{a'} Q(s', a') - Q(s, a)]
s <- s'
Until s is terminal
A central challenge in Q-learning is the exploration-exploitation trade-off: the agent must balance between exploiting its current best-known actions and exploring new actions that might yield higher returns. The Q-function is directly used by several exploration strategies to guide this balance.
| Strategy | Description | Advantages | Disadvantages |
|---|---|---|---|
| Epsilon-greedy | With probability epsilon, choose a random action; otherwise choose argmax_a Q(s, a) | Simple to implement and tune | Explores uniformly at random; does not prioritize promising actions |
| Boltzmann (softmax) | Sample actions from P(a) proportional to exp(Q(s, a) / tau), where tau is a temperature parameter | Assigns higher probability to actions with higher Q-values | Sensitive to temperature parameter tuning |
| Upper confidence bound (UCB) | Select argmax_a [Q(s, a) + c * sqrt(ln(t) / N(s, a))] | Explicitly accounts for uncertainty; efficient exploration | Requires visit counts; harder to apply with function approximation |
| Optimistic initialization | Initialize Q-values to high values, encouraging the agent to try all actions early | Simple; no extra computation | Effect diminishes over time |
The most commonly used strategy in practice is epsilon-greedy with a decaying epsilon, where epsilon starts high (more exploration) and gradually decreases toward zero (more exploitation) as the agent accumulates experience.
Q-learning is an off-policy algorithm because the update rule uses the maximum Q-value of the next state (corresponding to the greedy policy) regardless of what action the agent actually took. This means the agent can learn about the optimal policy while following a different, more exploratory behavior policy.
In contrast, SARSA (State-Action-Reward-State-Action) is an on-policy TD algorithm that updates the Q-function based on the action the agent actually takes in the next state:
Q(s, a) <- Q(s, a) + alpha * [ R + gamma * Q(s', a') - Q(s, a) ]
Here, a' is the action actually selected by the current policy in state s', rather than the action that maximizes Q. This distinction has practical consequences.
| Property | Q-learning (off-policy) | SARSA (on-policy) |
|---|---|---|
| Update target | max_{a'} Q(s', a') | Q(s', a') where a' is the action actually taken |
| Learns about | Optimal policy | Current policy (including exploration) |
| Convergence speed | Generally faster to optimal policy | Slower; converges to a policy that accounts for exploration |
| Safety during learning | May learn risky policies if exploration causes dangerous states | Learns safer policies because it accounts for exploratory actions |
| Classic example | In cliff-walking, learns the optimal (risky) path along the cliff edge | In cliff-walking, learns a safer path away from the cliff edge |
Expected SARSA is a variant that takes the expectation over all possible next actions weighted by the policy, rather than using a single sample. Its update target is sum_{a'} pi(a'|s') * Q(s', a'). Expected SARSA reduces variance compared to standard SARSA and, when using a greedy target policy, becomes equivalent to Q-learning.
Tabular Q-learning stores one Q-value for every state-action pair, which becomes infeasible when the state or action spaces are large or continuous. Function approximation addresses this by representing the Q-function with a parameterized model Q(s, a; theta), where theta is a vector of learnable parameters.
In linear Q-function approximation, the Q-value is expressed as a linear combination of hand-crafted features:
Q(s, a; theta) = theta^T * phi(s, a)
where phi(s, a) is a feature vector. Linear approximation is attractive because the loss function is convex, guaranteeing convergence to a global optimum under appropriate conditions. However, the quality of the learned Q-function depends heavily on the choice of features.
Greedy-GQ is a variant of Q-learning designed for use with linear function approximation that guarantees convergence, addressing the well-known instability of combining off-policy learning with function approximation (the "deadly triad").
Neural networks can automatically learn useful feature representations from raw inputs, eliminating the need for manual feature engineering. However, using nonlinear function approximators introduces instability: Tsitsiklis and Van Roy (1997) showed that Q-learning with nonlinear function approximation can diverge. Techniques such as experience replay, target networks, and gradient clipping are used to mitigate this instability.
The Deep Q-Network (DQN), introduced by Mnih et al. (2013) and refined in their 2015 Nature paper, was the first algorithm to successfully combine deep neural networks with Q-learning at scale. DQN used a convolutional neural network to learn Q-values directly from raw pixel inputs, achieving human-level performance on a range of Atari 2600 games.
DQN introduced two techniques to stabilize training with neural network function approximation:
Experience replay. The agent stores transitions (s, a, r, s') in a replay buffer and trains on randomly sampled mini-batches. This breaks temporal correlations between consecutive samples and allows each transition to be reused multiple times, improving data efficiency.
Target network. A separate copy of the Q-network, called the target network, is used to compute the TD target. The target network's parameters are updated periodically (e.g., every C steps) by copying the parameters from the main network. This prevents the target from changing too rapidly, which would otherwise cause training instability.
The DQN loss function is:
L(theta) = E[ (R + gamma * max_{a'} Q(s', a'; theta^-) - Q(s, a; theta))^2 ]
where theta^- denotes the parameters of the target network.
In the 2015 Nature paper, DQN achieved human-level performance on 29 out of 49 Atari games tested, using the same architecture and hyperparameters across all games. This demonstrated that a single RL agent could learn diverse skills directly from high-dimensional sensory input.
Following the original DQN, researchers developed several improvements that address specific weaknesses of the base algorithm.
Van Hasselt, Guez, and Silver (2016) showed that DQN tends to overestimate Q-values because the max operator in the target simultaneously selects and evaluates actions. Double DQN decouples these steps: the main network selects the best action, and the target network evaluates it:
Y = R + gamma * Q(s', argmax_{a'} Q(s', a'; theta); theta^-)
This simple change significantly reduces overestimation bias and improves performance.
Wang et al. (2016) proposed the Dueling Network Architecture, which separates the Q-function into two streams:
Q(s, a; theta, alpha, beta) = V(s; theta, beta) + A(s, a; theta, alpha) - mean_a A(s, a; theta, alpha)
One stream estimates the state-value function V(s), and the other estimates the advantage function A(s, a). This decomposition helps the network learn which states are valuable without needing to evaluate every action, particularly in states where the choice of action does not matter much.
Schaul et al. (2016) observed that sampling transitions uniformly from the replay buffer is suboptimal. Prioritized experience replay assigns higher sampling probability to transitions with larger TD errors, allowing the agent to learn more from surprising or informative experiences. This led to substantial performance improvements, increasing the median normalized score on Atari from 48% to 106%.
Bellemare, Dabney, and Munos (2017) proposed learning the full distribution of returns rather than just the expected value. The C51 algorithm represents the return distribution using 51 fixed atoms and learns the probability of each atom. Dabney et al. (2018) improved on this with QR-DQN (Quantile Regression DQN), which uses fixed uniform probabilities with learnable quantile locations, directly minimizing a quantile regression loss.
Fortuanto et al. (2018) replaced epsilon-greedy exploration with learned parametric noise injected into the network weights. This allows the network to learn how much exploration is appropriate for each state, resulting in more efficient state-dependent exploration.
Hessel et al. (2018) combined six DQN extensions into a single agent called Rainbow:
| Component | Purpose |
|---|---|
| Double Q-learning | Reduces overestimation bias |
| Prioritized experience replay | Focuses learning on informative transitions |
| Dueling networks | Separates state-value and advantage estimation |
| Multi-step learning | Uses n-step returns for faster reward propagation |
| Distributional RL (C51) | Learns the full return distribution |
| Noisy networks | Enables state-dependent exploration |
Rainbow achieved state-of-the-art performance on the Atari 2600 benchmark, outperforming each individual component by a large margin in both data efficiency and final performance.
Standard Q-learning requires computing max_a Q(s, a), which is straightforward when the action space is discrete and finite but becomes an optimization problem when actions are continuous.
Lillicrap et al. (2016) proposed DDPG, an actor-critic algorithm that maintains a Q-network (the critic) alongside a separate policy network (the actor). The actor learns a deterministic policy mu(s) that approximates argmax_a Q(s, a), avoiding the need to explicitly maximize over a continuous action space. DDPG uses experience replay and target networks, similar to DQN.
Gu et al. (2016) proposed NAF as a simpler alternative to DDPG. NAF parameterizes Q(s, a) as a quadratic function with respect to the action:
Q(s, a; theta) = V(s; theta) - (a - mu(s; theta))^T P(s; theta) (a - mu(s; theta))
where V(s) is the state value, mu(s) is the optimal action, and P(s) is a state-dependent positive-definite matrix. This quadratic form allows the maximum to be found in closed form: max_a Q(s, a) = V(s), achieved at a = mu(s). NAF showed faster and more stable learning than DDPG on several continuous control benchmarks.
Haarnoja et al. (2018) introduced the Soft Actor-Critic (SAC) algorithm, which uses a soft Q-function defined under the maximum entropy framework:
Q^pi_soft(s, a) = R(s, a) + gamma * E_{s'} [ V^pi_soft(s') ]
where the soft value function includes an entropy bonus:
V^pi_soft(s) = E_{a ~ pi} [ Q^pi_soft(s, a) - alpha * log pi(a|s) ]
The temperature parameter alpha controls the trade-off between reward maximization and entropy (policy randomness). SAC uses twin Q-networks (similar to Double Q-learning) to reduce overestimation and a stochastic policy, making it well-suited for continuous control tasks. SAC has become one of the most widely used algorithms for continuous control due to its stability and sample efficiency.
Fitted Q-iteration, introduced by Ernst, Geurts, and Wehenkel (2005), is a batch reinforcement learning algorithm that treats each iteration of Q-learning as a supervised regression problem. Given a fixed dataset of transitions {(s_i, a_i, r_i, s'i)}, FQI iteratively computes regression targets y_i = r_i + gamma * max{a'} Q_k(s'i, a') and fits a new regressor Q{k+1} to these targets. Any regression method (decision trees, neural networks, kernel methods) can be used as the function approximator.
Neural Fitted Q-iteration (NFQ), proposed by Riedmiller (2005), is a variant that uses multilayer perceptrons as the regressor, representing an early precursor to DQN.
In offline (or batch) RL, the agent cannot interact with the environment and must learn entirely from a fixed dataset. Naive application of Q-learning to offline data suffers from distribution shift: the Q-function may assign high values to state-action pairs that are poorly represented in the dataset. Algorithms such as Conservative Q-Learning (CQL), proposed by Kumar et al. (2020), address this by adding a regularizer that penalizes Q-values for out-of-distribution actions, producing a Q-function that lower-bounds the true value.
Several well-known challenges arise when learning or using Q-functions:
Curse of dimensionality. Tabular Q-learning requires storing and updating Q-values for every state-action pair. The number of entries grows exponentially with the dimensionality of the state and action spaces, making tabular methods impractical for most real-world problems.
Overestimation bias. The max operator in the Q-learning update systematically overestimates the true Q-values, especially in stochastic environments. Double Q-learning and related techniques mitigate this issue but do not eliminate it entirely.
The deadly triad. Sutton and Barto (2018) identified three factors that, when combined, can cause Q-learning to diverge: (1) function approximation, (2) bootstrapping (using estimated values in the update target), and (3) off-policy learning. All three are present in standard DQN, which is why experience replay and target networks are necessary for stability.
Sample efficiency. Model-free Q-learning algorithms typically require millions of environment interactions to learn good policies. Model-based methods, which learn a model of the environment's dynamics, can be more sample-efficient but introduce model bias.
Continuous actions. Computing max_a Q(s, a) is straightforward for discrete actions but requires solving a potentially non-convex optimization problem for continuous actions, leading to the development of actor-critic methods.
Reward shaping. The quality of the learned Q-function depends on the design of the reward signal. Sparse rewards (e.g., +1 for winning, 0 otherwise) make learning difficult because the agent receives no feedback on intermediate states.
Q-function-based algorithms have been applied across a wide range of domains:
| Domain | Example application | Algorithm used |
|---|---|---|
| Video games | Playing Atari 2600 games from raw pixels | DQN, Rainbow |
| Board games | Learning to play Go, chess, and shogi | AlphaZero (uses MCTS with Q-value estimates) |
| Robotics | Object manipulation and grasping | DDPG, SAC |
| Autonomous driving | Lane keeping and decision-making at intersections | Double DQN, DDPG |
| Resource management | Data center cooling optimization | DQN (Google DeepMind, 2016) |
| Finance | Portfolio optimization and trading strategies | Q-learning, DQN |
| Recommendation systems | Personalized content recommendations | Fitted Q-iteration |
| Natural language processing | Dialogue policy optimization | DQN |
| Year | Event |
|---|---|
| 1957 | Richard Bellman publishes the Bellman equation for dynamic programming |
| 1989 | Christopher Watkins introduces Q-learning in his PhD thesis at the University of Cambridge |
| 1992 | Watkins and Peter Dayan publish a convergence proof for Q-learning |
| 1994 | Rummery and Niranjan introduce SARSA |
| 2005 | Ernst et al. propose fitted Q-iteration; Riedmiller proposes Neural Fitted Q-iteration |
| 2010 | Van Hasselt proposes Double Q-learning |
| 2013 | Mnih et al. (DeepMind) publish the DQN paper, playing Atari from pixels |
| 2015 | Mnih et al. publish the refined DQN in Nature; Schaul et al. propose prioritized experience replay |
| 2016 | Van Hasselt et al. publish Double DQN; Wang et al. propose Dueling DQN; Lillicrap et al. propose DDPG; Gu et al. propose NAF |
| 2017 | Bellemare et al. introduce distributional RL with C51 |
| 2018 | Hessel et al. combine six improvements in Rainbow; Haarnoja et al. propose SAC; Dabney et al. propose QR-DQN |
| 2020 | Kumar et al. propose Conservative Q-Learning (CQL) for offline RL |