Reinforcement Learning: Agents, Rewards, and Q-Learning

Machine Learning Machine Learning 7 min read 1463 words Beginner ExcellentWiki Editorial Team

Reinforcement learning (RL) is a paradigm where an agent learns to make sequential decisions by interacting with an environment, receiving rewards or penalties based on its actions. Unlike supervised learning, which learns from labeled examples, RL discovers effective strategies through trial and error — the agent must explore unknown actions to discover their consequences while exploiting known good actions to accumulate reward.

The modern RL framework builds on the Markov decision process formalism developed by Richard Bellman in the 1950s and the dynamic programming solutions he proposed. The field exploded after DeepMind’s DQN (Mnih et al., 2015) achieved human-level performance on Atari games, followed by AlphaGo’s defeat of world champion Lee Sedol in 2016. RL now powers breakthroughs in robotics, game playing, autonomous driving, and resource optimization.

Formal RL Problem Statement Formulation

Reinforcement learning can be formalized as an optimal control problem where the agent maximizes cumulative discounted reward. The expected return starting from state s under policy pi is defined as:

G_t = E[sum_{k=0}^{infinity} gamma^k × R_{t+k+1} | S_t = s, pi]

The agent does not know the transition probabilities or reward function in advance — it must learn them through interaction. This distinguishes RL from planning problems where the environment dynamics are given. The exploration-exploitation dilemma — should the agent try new actions or stick with known good ones — is the central challenge that makes RL fundamentally harder than supervised or unsupervised learning.

Key Concepts

The RL Loop

The agent exists in an environment. At each time step, the agent observes the current state, selects an action, and receives a reward and the next state. This cycle continues until a terminal condition is reached:

# Simplified RL loop
state = env.reset()
done = False
total_reward = 0

while not done:
    action = agent.select_action(state)
    next_state, reward, done, info = env.step(action)
    agent.update(state, action, reward, next_state, done)
    state = next_state
    total_reward += reward

Markov Decision Process

MDPs formalize RL problems with five components:

States (S): all possible situations the agent can encounter
Actions (A): all choices available to the agent
Transition function P(s’ | s, a): probability of moving to state s’ given action a in state s
Reward function R(s, a, s’): immediate reward received for transitioning
Discount factor gamma: how much future rewards are worth relative to immediate rewards (range 0 to 1)

The agent’s goal is to learn a policy pi(a | s) — a mapping from states to actions — that maximizes the expected cumulative discounted reward, also called the return.

Value Functions

Value functions estimate expected future reward. The state-value function V-pi(s) is the expected return starting from state s and following policy pi. The action-value function Q-pi(s, a) is the expected return starting from state s, taking action a, then following policy pi.

The Bellman optimality equation provides a recursive relationship that the optimal Q-function must satisfy:

Q*(s, a) = E[R(s, a, s') + gamma × max Q*(s', a') | s, a]

This equation is the foundation of Q-learning and many other RL algorithms.

Model-Free vs. Model-Based RL

Model-free RL learns directly from experience without explicitly modeling the environment dynamics. It is simpler to implement and works well when the environment is complex or unknown. Q-learning and policy gradients are model-free.

Model-based RL learns a model of the environment — predicting next states and rewards — and uses this model for planning. Model-based approaches are more sample-efficient but the learned model introduces approximation errors. MuZero (Schrittwieser et al., 2020) combines both by learning a model that predicts only the quantities needed for planning.

Q-Learning

Q-learning (Watkins & Dayan, 1992) is a model-free algorithm that learns the optimal action-value function directly. It is off-policy, meaning it can learn from actions taken under any policy, not just the current one:

import gymnasium as gym
import numpy as np

env = gym.make('Taxi-v3', render_mode='rgb_array')
n_states = env.observation_space.n  # 500 states
n_actions = env.action_space.n       # 6 actions

Q = np.zeros((n_states, n_actions))
alpha = 0.1      # Learning rate
gamma = 0.9     # Discount factor
epsilon = 1.0   # Exploration rate
epsilon_decay = 0.995
min_epsilon = 0.01

for episode in range(5000):
    state, _ = env.reset()
    done = False
    total_reward = 0

    while not done:
        if np.random.random() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state])

        next_state, reward, done, truncated, _ = env.step(action)
        done = done or truncated

        # Q-learning update
        td_target = reward + gamma * np.max(Q[next_state]) * (not done)
        td_error = td_target - Q[state, action]
        Q[state, action] += alpha * td_error

        state = next_state
        total_reward += reward

    epsilon = max(min_epsilon, epsilon * epsilon_decay)

The Q-learning update uses the Bellman optimality equation as the target. The learning rate alpha controls how quickly Q-values are updated. The discount factor gamma determines how far-sighted the agent is.

Deep Q-Networks

DQN extends Q-learning to high-dimensional state spaces by using a neural network to approximate the Q-function. Mnih et al. (2015) introduced two key innovations that made deep RL stable:

Experience Replay

Store past experiences in a replay buffer and sample randomly for training. This breaks the temporal correlations between consecutive experiences and improves data efficiency:

from collections import deque
import random

class ReplayBuffer:
    def __init__(self, capacity=10000):
        self.buffer = deque(maxlen=capacity)

    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))

    def sample(self, batch_size):
        batch = random.sample(self.buffer, batch_size)
        states, actions, rewards, next_states, dones = zip(*batch)
        return (np.array(states), np.array(actions), np.array(rewards),
                np.array(next_states), np.array(dones))

Target Network

A separate target network with frozen parameters provides stable Q-targets. The target network is periodically updated to match the online network. This prevents the moving target problem where Q-targets change every update step.

Policy Gradient Methods

Policy gradient methods directly optimize the policy without learning a value function. They compute the gradient of expected reward with respect to policy parameters and perform gradient ascent:

def reinforce(env, policy, optimizer, episodes=1000, gamma=0.99):
    for episode in range(episodes):
        states, actions, rewards = [], [], []
        state, _ = env.reset()
        done = False

        while not done:
            action_probs = policy(torch.FloatTensor(state))
            action = torch.multinomial(action_probs, 1).item()
            next_state, reward, done, truncated, _ = env.step(action)
            states.append(state)
            actions.append(action)
            rewards.append(reward)
            state = next_state

        # Compute discounted returns
        returns = []
        G = 0
        for r in reversed(rewards):
            G = r + gamma * G
            returns.insert(0, G)

        # Policy gradient update
        returns = torch.FloatTensor(returns)
        # ... normalize returns, compute loss, backward step

Actor-Critic Methods

Actor-Critic combines value-based and policy-based approaches. The actor learns the policy (what to do), and the critic evaluates the policy by estimating the value function (how good the current state is). Proximal Policy Optimization (Schulman et al., 2017) is the most widely used actor-critic algorithm, clipping policy updates to a trust region for stable training.

Exploration vs. Exploitation

The agent must balance exploring new actions to discover potentially better strategies with exploiting actions known to produce high reward. Common exploration strategies:

Epsilon-greedy: take a random action with probability epsilon, decaying over time
Boltzmann exploration: sample actions proportionally to their estimated Q-values
Noise-based exploration (continuous actions): add Gaussian noise to actions
Entropy bonus (policy gradients): add a penalty for overly confident policies to encourage exploration

FAQ

What is the difference between reinforcement learning and supervised learning? Supervised learning learns from labeled data (input-output pairs provided by an expert). RL learns from rewards received during interaction — the agent must discover which actions lead to reward through experience, without being told the correct action.

Why does RL need so much data? The agent must try many actions to discover their long-term consequences. Unlike supervised learning, where each example provides a direct signal, RL provides only sparse rewards with a delayed credit assignment problem — knowing which earlier actions led to a later reward is fundamentally harder.

What is the difference between on-policy and off-policy? On-policy algorithms evaluate and improve the same policy that is generating actions. Off-policy algorithms can learn from data generated by any policy (including historical data or other agents). Q-learning and DQN are off-policy. PPO and A2C are on-policy. Off-policy is more sample-efficient; on-policy is more stable.

How do I design a reward function? Reward shaping is both art and science. The reward should be a faithful signal of the desired outcome. Avoid “reward hacking” — where the agent finds unexpected ways to maximize reward without achieving the intended goal. Start sparse (reward only on success) and add shaping rewards carefully.

What hardware do I need for deep RL? DQN on Atari games runs on a single GPU. MuZero and large-scale RL require multiple GPUs or TPUs. For learning, start with simple environments like CartPole or LunarLander that train in minutes on a CPU.