# Q-Learning

Q-learning is a model-free reinforcement learning algorithm that learns an optimal action-selection policy for finite Markov decision processes by estimating the expected reward (quality) of actions in states, without requiring an environment model.

Q-learning is a model-free reinforcement learning algorithm that trains an agent to assign values to its possible actions based on its current state, without requiring a model of the environment. It can handle problems with stochastic transitions and rewards without requiring adaptations. For any finite Markov decision process, Q-learning finds an optimal policy in the sense of maximizing the expected value of the total reward over any and all successive steps, starting from the current state, given infinite exploration time and a partly random policy. The "Q" refers to the function the algorithm computes: the expected reward - that is, the quality - of an action taken in a given state.

In a simple example, a grid maze agent learns to reach an exit worth 10 points. At a junction, Q-learning might assign a higher value to moving right than left if right gets to the exit faster, improving this choice by trying both directions over time. This illustrates how the algorithm balances immediate reward against long-term outcomes through iterative updates.

## Reinforcement Learning Context

Reinforcement learning involves an agent, a set of states \(\mathcal{S}\), and a set \(\mathcal{A}\) of actions per state. By performing an action \(a \in \mathcal{A}\), the agent transitions from state to state. Executing an action in a specific state provides the agent with a reward, a numerical score. The goal of the agent is to maximize its total reward by adding the maximum reward attainable from future states to the reward for achieving its current state, effectively influencing the current action by the potential future reward. This potential reward is a weighted sum of expected values of the rewards of all future steps starting from the current state.

As an example, consider boarding a train, where the reward is measured by the negative of total boarding time. One strategy is to enter the train door as soon as it opens, minimizing initial wait time. If the train is crowded, however, entry is slow as departing passengers fight to leave. The total boarding time is then 0 seconds wait plus 15 seconds fight time. On the next day, by random chance (exploration), the agent waits and lets others depart first, resulting in a longer wait but less fighting time. Overall, this path has a higher reward since total boarding time is 5 seconds wait plus 0 seconds fight time. Through exploration, despite the initial patient action resulting in a larger cost than the forceful strategy, the overall cost is lower, revealing a more rewarding strategy.

## Algorithm Mechanics

After \(\Delta t\) steps into the future, the agent will decide some next step. The weight for this step is calculated as \(\gamma^{\Delta t}\), where \(\gamma\) (the discount factor) is a number between 0 and 1. Assuming \(\gamma < 1\), it values rewards received earlier higher than those received later, reflecting the value of a good start. \(\gamma\) may also be interpreted as the probability to succeed or survive at every step \(\Delta t\).

The algorithm has a function that calculates the quality of a state-action combination: \(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\). Before learning begins, \(Q\) is initialized to a possibly arbitrary fixed value chosen by the programmer. At each time \(t\), the agent selects an action \(A_t\), observes a reward \(R_{t+1}\), enters a new state \(S_{t+1}\) (which may depend on both the previous state \(S_t\) and the selected action), and \(Q\) is updated. The core update is a Bellman equation as a simple value iteration update, using the weighted average of the current value and the new information:

\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)

where \(\alpha\) is the learning rate, controlling how much new information overrides old information.

## Exploration and Exploitation

The algorithm relies on a balance between exploration (trying new actions to discover their rewards) and exploitation (choosing actions known to yield high rewards). A partly random policy, such as epsilon-greedy, selects the best-known action most of the time but occasionally picks a random action to explore. This ensures the agent can improve its estimates over time, as seen in the train boarding example where random exploration revealed a better strategy.

## Convergence and Optimality

For any finite Markov decision process, Q-learning converges to an optimal policy that maximizes the expected total reward from any starting state, provided infinite exploration time and a suitable learning rate schedule. The algorithm does not require a model of the environment's transition dynamics, making it applicable to problems where such a model is unknown or complex. This model-free property distinguishes it from model-based methods that need explicit transition probabilities.

## Applications and Extensions

Q-learning has been applied in robotics, game playing, and autonomous systems. Its tabular form works for small state spaces, but for large or continuous spaces, extensions like deep Q-networks combine Q-learning with [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) and [neural-network](https://www.wikiprompt.org/wiki/neural-network) function approximators. These advances have enabled successes in domains such as [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) game agents and [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) control tasks. The algorithm's principles also underpin modern [reinforcement-learning](https://www.wikiprompt.org/wiki/reinforcement-learning) research at institutions like [berkeley-ai-research](https://www.wikiprompt.org/wiki/berkeley-ai-research) and [mit-csail](https://www.wikiprompt.org/wiki/mit-csail).

---
Source: https://www.wikiprompt.org/wiki/q-learning
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-07T02:33:13.840641+00:00