# Q-Function

> Source: https://aiwiki.ai/wiki/q-function
> Updated: 2026-07-11
> Categories: Machine Learning, Reinforcement Learning
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/)
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution to "AI Wiki (aiwiki.ai)".

The **Q-function**, also called the **action-value function** or **state-action value function** and written $$Q(s, a)$$, is the function in [reinforcement learning](/wiki/reinforcement_learning) (RL) that returns the expected cumulative discounted reward an agent earns by taking action a in state s and then following a policy thereafter. It is the action-conditioned counterpart of the [state-value function](/wiki/state) $$V(s)$$: whereas $$V(s)$$ scores how good a state is, $$Q(s, a)$$ scores how good each available action is from that state, so $$V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s, a)$$. The optimal action-value function $$Q^*(s, a)$$ yields an optimal policy directly by greedy selection, $$\pi^*(s) = \arg\max_a Q^*(s, a)$$, which makes the Q-function the engine behind value-based control algorithms such as [Q-learning](/wiki/q-learning) [1] and [Deep Q-Networks](/wiki/deep_q-network_dqn) [4].

The concept was formalized by Christopher Watkins in his 1989 Cambridge PhD thesis "Learning from Delayed Rewards," where it underpinned the Q-learning algorithm; Watkins and Peter Dayan proved its convergence in 1992 [1][2]. In 2013-2015, Volodymyr Mnih and colleagues at DeepMind scaled the Q-function to raw pixels with the Deep Q-Network, achieving human-level play on 49 Atari 2600 games using a single architecture and one set of hyperparameters [3][4].

This article focuses on the Q-function as the engine behind value-based control algorithms: how it is learned from experience, how it is approximated at scale, and the algorithmic family it has spawned. For a complementary treatment that emphasizes the mathematical theory (Monte Carlo versus temporal-difference estimation, the contraction-mapping convergence argument, and the maximization-bias analysis), see the companion article on the [state-action value function](/wiki/state-action_value_function).

## Explain like I'm 5 (ELI5)

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](/wiki/neural_network)) to memorize the patterns on the cheat sheet instead of writing everything down. That is what a Deep Q-Network does.

## What is a Q-function? (formal definition)

Given a [Markov decision process](/wiki/markov_decision_process_mdp) (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](/wiki/gamma) ($$0 \le \gamma < 1$$), the Q-function under a policy $$\pi$$ is defined as [11]:

$$
Q^\pi(s, a) = \mathbb{E}_\pi\left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \mid s_0 = s, a_0 = a \right]
$$

Here, $$\mathbb{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) = \arg\max_a Q^*(s, a)
$$

## How does the Q-function differ from the value function?

The Q-function is closely related to two other functions that appear throughout reinforcement learning theory. The defining difference is what each function is conditioned on: the state-value function depends on the state alone, while the action-value (Q) function additionally fixes the first action.

| 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 |

### State-value function

The [state-value function](/wiki/state) $$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 \mid s) Q^\pi(s, a)
$$

For the optimal value function, $$V^*(s) = \max_a Q^*(s, a)$$. This identity is what makes the Q-function more convenient than V for control: because Q already conditions on the action, an agent can pick the best action by comparing Q-values directly, without needing a model of the environment to look one step ahead. Acting greedily on V, by contrast, requires knowing the transition dynamics P.

### Advantage function

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.

## What is the Bellman equation for the Q-function?

The Q-function satisfies a recursive relationship known as the [Bellman equation](/wiki/bellman_equation), first introduced by Richard Bellman in his 1957 work on dynamic programming [12], which decomposes the value of a state-action pair into an immediate reward plus the discounted expected future value.

### Bellman expectation equation

For a given policy $$\pi$$:

$$
Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \sum_{a'} \pi(a' \mid 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.

### Bellman optimality equation

The optimal Q-function satisfies a nonlinear version of the Bellman equation:

$$
Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid 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. Sutton and Barto note that the Bellman optimality equation is, in principle, solvable for the optimal value function given a complete and accurate model of the environment's dynamics; most of reinforcement learning is concerned with approximating its solution when that model is unknown [11].

## How is the Q-function learned? (tabular Q-learning)

[Q-learning](/wiki/q-learning), introduced by Christopher Watkins in his 1989 PhD thesis "Learning from Delayed Rewards" at King's College, University of Cambridge [1], 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. It belongs to the broader family of [temporal difference](/wiki/temporal_difference_learning) control methods; the trade-offs between TD bootstrapping and Monte Carlo estimation of Q-values are discussed in detail in the [state-action value function](/wiki/state-action_value_function) article.

### Update rule

The agent maintains a table of Q-values (one entry per state-action pair) and updates them after each transition using [temporal difference](/wiki/temporal_difference_learning) (TD) learning:

$$
Q(s, a) \leftarrow Q(s, a) + \alpha [ R + \gamma \max_{a'} Q(s', a') - Q(s, a) ]
$$

In this equation:

- $$\alpha$$ is the [learning rate](/wiki/learning_rate) ($$0 < \alpha \le 1$$), controlling how much new information overrides the old estimate. A learning rate of 0 means the agent learns nothing; a learning rate of 1 means the agent considers only the most recent information.
- $$R$$ is the immediate reward received after taking action a in state s.
- $$s'$$ is the next state the agent transitions to.
- $$\max_{a'} Q(s', a')$$ is the maximum Q-value achievable from the next state, representing the best possible future return.
- The quantity in brackets, $$R + \gamma \max_{a'} Q(s', a') - Q(s, a)$$, is called the **TD error**.

This update is **off-policy** and uses **TD(0)** bootstrapping: the target $$R + \gamma \max_{a'} Q(s', a')$$ is built from the agent's own current estimate of the next state's best value (one step of lookahead), and it follows the greedy action $$\max_{a'}$$ rather than the exploratory action the agent actually took.

### Convergence

Watkins and Dayan (1992) proved that tabular Q-learning converges to the optimal Q-function $$Q^*$$ with probability 1, provided that [2]:

1. All state-action pairs are visited infinitely often.
2. The learning rate satisfies the Robbins-Monro conditions: $$\sum \alpha_t = \infty$$ and $$\sum \alpha_t^2 < \infty$$.
3. The rewards are bounded.

These conditions ensure that the algorithm explores enough of the state-action space and that the updates diminish over time, preventing oscillation. As Watkins and Dayan summarize the result, "Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action-values are represented discretely" [2]. The proof rests on the fact that the Bellman optimality operator is a $$\gamma$$-contraction in the supremum norm, so repeated application drives any initial estimate toward the unique fixed point $$Q^*$$ (this contraction argument is developed in the companion [state-action value function](/wiki/state-action_value_function) article). It was among the first rigorous convergence guarantees for a reinforcement learning control algorithm, establishing Q-learning as a theoretically grounded method rather than a heuristic [2].

### Algorithm pseudocode

```
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
```

## How does the Q-function guide exploration?

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 $$\arg\max_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 $$\arg\max_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](/wiki/epsilon_greedy_policy) with a decaying $$\epsilon$$, where $$\epsilon$$ starts high (more exploration) and gradually decreases toward zero (more exploitation) as the agent accumulates experience.

## What is the difference between on-policy and off-policy Q-functions?

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), first described by Rummery and Niranjan in a 1994 Cambridge technical report under the name Modified Connectionist Q-Learning [16], 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) \leftarrow 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' \mid s') Q(s', a')$$. Expected SARSA reduces variance compared to standard SARSA and, when using a greedy target policy, becomes equivalent to Q-learning.

## How is the Q-function approximated at scale? (function approximation)

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.

### Linear function approximation

In linear Q-function approximation, the Q-value is expressed as a linear combination of hand-crafted features:

$$
Q(s, a; \theta) = \theta^\top \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 network approximation

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 temporal-difference learning combined with a nonlinear function approximator can diverge [17]. Techniques such as [experience replay](/wiki/experience_replay), [target networks](/wiki/target_network), and gradient clipping are used to mitigate this instability.

## What is a Deep Q-Network (DQN)?

The [Deep Q-Network](/wiki/deep_q-network_dqn) (DQN), introduced by Mnih et al. (2013) [3] and refined in their 2015 Nature paper [4], 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. The authors describe the result as bridging "the divide between high-dimensional sensory inputs and actions, resulting in the first artificial agent that is capable of learning to excel at a diverse array of challenging tasks" [4].

### Key innovations

DQN introduced two techniques to stabilize training with neural network function approximation:

1. **Experience replay.** The agent stores transitions (s, a, r, s') in a [replay buffer](/wiki/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. In the canonical Atari configuration the buffer held the most recent one million frames [4].

2. **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 $$\theta^-$$ are held fixed and refreshed periodically (every $$C$$ steps) by copying the parameters from the main network; the Nature agent used $$C = 10{,}000$$ [4]. This prevents the target from changing too rapidly, which would otherwise cause training instability.

The DQN loss function is:

$$
L(\theta) = \mathbb{E}\left[ (R + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta))^2 \right]
$$

where $$\theta^-$$ denotes the parameters of the target network.

### Results

In the 2015 Nature paper, DQN was evaluated on 49 Atari games using a single architecture and one set of hyperparameters. It outperformed the best prior reinforcement learning methods on 43 of the games without using any of the game-specific prior knowledge that earlier approaches relied on, and it reached more than 75 percent of a professional human games tester's score on 29 of the 49 games [4]. This demonstrated that a single RL agent could learn diverse skills directly from high-dimensional sensory input.

## What are the main DQN extensions and variants?

Following the original DQN, researchers developed several improvements that address specific weaknesses of the base algorithm.

### Double DQN

The underlying idea predates deep learning. Hado van Hasselt's 2010 Double Q-learning paper showed that the single max operator produces a positive maximization bias, and that maintaining two independent estimators (one to select the maximizing action, the other to evaluate it) removes that systematic overestimation [18]. The paper's roulette illustration is striking: an action whose true expected value is negative was still estimated by ordinary Q-learning to be worth almost ten dollars even after 100,000 plays, whereas Double Q-learning tracked the correct sign [18].

Van Hasselt, Guez, and Silver (2016) carried this idea into deep networks [5]. They showed that DQN tends to overestimate Q-values because the max operator in the target simultaneously selects and evaluates actions, and Double DQN decouples these steps by reusing the existing online and target networks: the main network selects the best action, and the target network evaluates it:

$$
Y = R + \gamma Q(s', \arg\max_{a'} Q(s', a'; \theta); \theta^-)
$$

This simple change significantly reduces overestimation bias and improves performance across the Atari suite [5]. A deeper analysis of why the max operator overestimates (its connection to Jensen's inequality and the winner's curse) appears in the [state-action value function](/wiki/state-action_value_function) article.

### Dueling DQN

Wang et al. (2016) proposed the Dueling Network Architecture, which separates the Q-function into two streams [6]:

$$
Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta) + A(s, a; \theta, \alpha) - \mathrm{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.

### Prioritized experience replay

Schaul et al. (2016) observed that sampling transitions uniformly from the replay buffer is suboptimal [7]. Prioritized experience replay assigns higher sampling probability to transitions with larger TD errors, allowing the agent to learn more from surprising or informative experiences. Importance-sampling weights are used to correct the bias this non-uniform sampling introduces. When added to DQN, it raised the median human-normalized score on the Atari benchmark from 48 percent to 106 percent and improved performance on 41 of the 49 games [7].

### Distributional Q-learning

Bellemare, Dabney, and Munos (2017) proposed learning the full distribution of returns rather than just the expected value [13]. 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 [19].

### Noisy networks

Fortunato et al. (2018) replaced epsilon-greedy exploration with learned parametric noise injected into the network weights [20]. The noise parameters are trained by gradient descent alongside the ordinary weights, so the network learns how much exploration is appropriate for each state, resulting in more efficient state-dependent exploration. The paper uses a factorised Gaussian noise scheme to keep the number of extra random variables low (one per input and one per output of each noisy layer rather than one per weight) [20].

### Rainbow DQN

Hessel et al. (2018) combined six DQN extensions into a single agent called Rainbow [8]:

| 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. An ablation study in the same paper found that prioritized experience replay and multi-step learning were the two most important components: removing either caused the largest drop in median performance [8].

## How is the Q-function used in continuous action spaces?

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.

### Deep Deterministic Policy Gradient (DDPG)

Lillicrap et al. (2016) proposed DDPG, an actor-[critic](/wiki/critic) algorithm that maintains a Q-network (the critic) alongside a separate policy network (the actor) [15]. The actor learns a deterministic policy $$\mu(s)$$ that approximates $$\arg\max_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.

### Normalized Advantage Functions (NAF)

Gu et al. (2016) proposed NAF as a simpler alternative to DDPG [21]. 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))^\top 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.

### Soft Q-function and SAC

Haarnoja et al. (2018) introduced the Soft Actor-Critic (SAC) algorithm, which uses a **soft Q-function** defined under the maximum entropy framework [9]:

$$
Q^\pi_{\mathrm{soft}}(s, a) = R(s, a) + \gamma \mathbb{E}_{s'}\left[ V^\pi_{\mathrm{soft}}(s') \right]
$$

where the soft value function includes an entropy bonus:

$$
V^\pi_{\mathrm{soft}}(s) = \mathbb{E}_{a \sim \pi}\left[ Q^\pi_{\mathrm{soft}}(s, a) - \alpha \log \pi(a \mid s) \right]
$$

The temperature parameter $$\alpha$$ controls the trade-off between reward maximization and entropy (policy randomness). A distinctive feature of the maximum entropy setting is that the hard max in the ordinary Bellman optimality equation is replaced by a "soft" maximum, the log-sum-exp operator: $$V_{\mathrm{soft}}(s) = \alpha \log \sum_a \exp(Q_{\mathrm{soft}}(s, a) / \alpha)$$. This soft maximum reduces to the ordinary max as the temperature $$\alpha$$ goes to zero, and it makes the optimal soft policy a Boltzmann distribution over Q-values. The soft Q-function was first developed in the soft Q-learning framework of Haarnoja et al. (2017), which expressed the optimal policy as an energy-based model defined by the Q-function [22]. SAC uses twin Q-networks and takes the minimum of the two estimates (the same mechanism as Double Q-learning and TD3) to reduce overestimation, together with a stochastic policy, making it well-suited for continuous control tasks [9]. SAC has become one of the most widely used algorithms for continuous control due to its stability and sample efficiency.

## How is the Q-function learned from a fixed dataset? (batch and offline methods)

### Fitted Q-iteration (FQI)

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 [10]. 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 and updates them with the Rprop batch optimizer, representing an early precursor to DQN [23].

### Offline reinforcement learning

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, and because the bootstrapped target maximizes over actions, these inflated estimates feed back into the update and compound. 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 [14].

## What are the challenges and limitations of Q-functions?

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 [18].

- **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 [11]. 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.

## What is the Q-function used for? (applications)

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 (Google DeepMind reported a 40 percent cut in cooling energy in 2016) [24] | DQN |
| Finance | Portfolio optimization and trading strategies | Q-learning, DQN |
| Recommendation systems | Personalized content recommendations | Fitted Q-iteration |
| Natural language processing | Dialogue policy optimization | DQN |

## When was the Q-function developed? (historical timeline)

| 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 (as Modified Connectionist Q-Learning) |
| 1997 | Tsitsiklis and Van Roy analyze TD learning with function approximation and show divergence is possible with nonlinear approximators |
| 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; Haarnoja et al. introduce soft Q-learning |
| 2018 | Hessel et al. combine six improvements in Rainbow; Haarnoja et al. propose SAC; Dabney et al. propose QR-DQN; Fortunato et al. propose noisy networks |
| 2020 | Kumar et al. propose Conservative Q-Learning (CQL) for offline RL |

## See also

- [Reinforcement learning](/wiki/reinforcement_learning)
- [State-action value function](/wiki/state-action_value_function)
- [Q-learning](/wiki/q-learning)
- [Deep Q-Network (DQN)](/wiki/deep_q-network_dqn)
- [SARSA](/wiki/sarsa)
- [Temporal difference learning](/wiki/temporal_difference_learning)
- [Bellman equation](/wiki/bellman_equation)
- [Markov decision process](/wiki/markov_decision_process_mdp)
- [Policy](/wiki/policy)
- [Reward](/wiki/reward)
- [Discount factor (gamma)](/wiki/gamma)
- [Experience replay](/wiki/experience_replay)
- [Target network](/wiki/target_network)
- [Epsilon-greedy policy](/wiki/epsilon_greedy_policy)

## References

1. Watkins, C. J. C. H. (1989). "Learning from Delayed Rewards." PhD Thesis, King's College, University of Cambridge. https://www.cs.rhul.ac.uk/~chrisw/thesis.html
2. Watkins, C. J. C. H., & Dayan, P. (1992). "Q-Learning." *Machine Learning*, 8(3-4), 279-292. https://link.springer.com/article/10.1007/BF00992698
3. Mnih, V., et al. (2013). "Playing Atari with Deep Reinforcement Learning." arXiv preprint arXiv:1312.5602. https://arxiv.org/abs/1312.5602
4. Mnih, V., et al. (2015). "Human-level control through deep reinforcement learning." *Nature*, 518(7540), 529-533. https://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf
5. Van Hasselt, H., Guez, A., & Silver, D. (2016). "Deep Reinforcement Learning with Double Q-learning." *Proceedings of the AAAI Conference on Artificial Intelligence*, 30(1). https://arxiv.org/abs/1509.06461
6. Wang, Z., et al. (2016). "Dueling Network Architectures for Deep Reinforcement Learning." *Proceedings of the 33rd International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1511.06581
7. Schaul, T., et al. (2016). "Prioritized Experience Replay." *Proceedings of the International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1511.05952
8. Hessel, M., et al. (2018). "Rainbow: Combining Improvements in Deep Reinforcement Learning." *Proceedings of the AAAI Conference on Artificial Intelligence*. https://arxiv.org/abs/1710.02298
9. Haarnoja, T., et al. (2018). "Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor." *Proceedings of the 35th International Conference on Machine Learning (ICML)*. https://proceedings.mlr.press/v80/haarnoja18b/haarnoja18b.pdf
10. Ernst, D., Geurts, P., & Wehenkel, L. (2005). "Tree-Based Batch Mode Reinforcement Learning." *Journal of Machine Learning Research*, 6, 503-556. https://www.jmlr.org/papers/volume6/ernst05a/ernst05a.pdf
11. Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.). MIT Press. http://incompleteideas.net/book/the-book-2nd.html
12. Bellman, R. (1957). *Dynamic Programming*. Princeton University Press.
13. Bellemare, M. G., Dabney, W., & Munos, R. (2017). "A Distributional Perspective on Reinforcement Learning." *Proceedings of the 34th International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1707.06887
14. Kumar, A., et al. (2020). "Conservative Q-Learning for Offline Reinforcement Learning." *Advances in Neural Information Processing Systems (NeurIPS)* 33. https://arxiv.org/abs/2006.04779
15. Lillicrap, T. P., et al. (2016). "Continuous control with deep reinforcement learning." *Proceedings of the International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1509.02971
16. Rummery, G. A., & Niranjan, M. (1994). "On-line Q-learning Using Connectionist Systems." Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department. http://mi.eng.cam.ac.uk/reports/svr-ftp/auto-pdf/rummery_tr166.pdf
17. Tsitsiklis, J. N., & Van Roy, B. (1997). "An Analysis of Temporal-Difference Learning with Function Approximation." *IEEE Transactions on Automatic Control*, 42(5), 674-690. https://web.mit.edu/jnt/www/Papers/J063-97-bvr-td.pdf
18. Van Hasselt, H. (2010). "Double Q-learning." *Advances in Neural Information Processing Systems (NeurIPS)* 23. https://proceedings.neurips.cc/paper/2010/hash/091d584fced301b442654dd8c23b3fc9-Abstract.html
19. Dabney, W., Rowland, M., Bellemare, M. G., & Munos, R. (2018). "Distributional Reinforcement Learning with Quantile Regression." *Proceedings of the AAAI Conference on Artificial Intelligence*, 32(1). https://arxiv.org/abs/1710.10044
20. Fortunato, M., et al. (2018). "Noisy Networks for Exploration." *Proceedings of the International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1706.10295
21. Gu, S., Lillicrap, T., Sutskever, I., & Levine, S. (2016). "Continuous Deep Q-Learning with Model-based Acceleration." *Proceedings of the 33rd International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1603.00748
22. Haarnoja, T., Tang, H., Abbeel, P., & Levine, S. (2017). "Reinforcement Learning with Deep Energy-Based Policies." *Proceedings of the 34th International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1702.08165
23. Riedmiller, M. (2005). "Neural Fitted Q Iteration: First Experiences with a Data Efficient Neural Reinforcement Learning Method." *Machine Learning: ECML 2005*, LNCS 3720, 317-328. https://link.springer.com/chapter/10.1007/11564096_32
24. Evans, R., & Gao, J. (2016). "DeepMind AI Reduces Google Data Centre Cooling Bill by 40%." Google DeepMind Blog. https://deepmind.google/blog/deepmind-ai-reduces-google-data-centre-cooling-bill-by-40/